Q:

C++ print Postorder traversal from Preorder and Inorder traversal of a tree

mahmoud2506
Save to bookmark
|
2022-05-08
|
  430 
0

Given Preorder and Inorder traversal of the tree

For Example: A tree is given

tree

Inorder traversal of the given tree is: - 9, 20, 29, 30, 50, 90, 100, 120
Preorder traversal of the given tree is: - 30, 20, 9, 29, 90, 50, 120, 100
Postorder traversal of the given tree is: - 9, 29, 20, 50, 100, 120, 90, 30
C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-08
need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

As we know that in preorder traversal root is always the first element so we will find the left and right subtree recursively and at last the root, for that we have to search inorder for the left and right subtree. First we will search elements of preorder in inorder as the elements after the index of the searched element in inorder are the members of the right subtree and elements before the index are elements of right subtree and the searched element is the root of that subtree.

Consider the program:

#include<iostream>
using namespace std;

/*Find x in inOrder*/
int search(int arr[],int x,int n)   
{
	int i;
	for(i=0;i<n;i++)
	{
		if(arr[i]==x)
		 return i; /*return the index of the element found*/
	}
	return -1;                      
}

void printPostOrder(int inOrder[],int preOrder[],int n)
{
	int rootNode=search(inOrder,preOrder[0],n);
	if(rootNode)	/*If right subtree is not empty */
	{	
		printPostOrder(inOrder,preOrder+1,rootNode);
	}
	if(rootNode!=n-1)	/*If left subtree is not empty*/
	{	
		printPostOrder(inOrder+rootNode+1,preOrder+rootNode+1,n-rootNode-1);
	}
	cout<<preOrder[0]<<" ";          
}

int main()
{
	int inOrder[]={9,20,29,30,50,90,100,120};
	int preOrder[]={30,20,9,29,90,50,120,100};
	
	int n=sizeof(inOrder)/sizeof(inOrder[0]);
	
	cout<<"Post order : ";
	printPostOrder(inOrder,preOrder,n);
	cout<<endl;
	
	return 0;
}

Output

 
Post order : 9 29 20 50 100 120 90 30

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Data Structure programs using C and C++ (Sorting Programs)
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Infix To Postfix Conversion Using Stack [with C pr... >>
<< Dijkstra\'s Algorithm: Explanation and Implem...