











Construct Tree From Given Postorder And Preorder Traversal In C++
Construct Tree From Given Postorder And Preorder Traversal in C++
There are three types of traversals in a tree: Inorder, Preorder and Postorder Traversal. In this article, a tree is constructed using postorder and preorder traversal.
Preorder Traversal – We first print the node,then move to the left subtree and finally to the right subtree.
Postorder Traversal – Left and right subtree is visited first and then the node is printed.


Algorithm For PreOrder Traversal:
- Print the node.
- Traverse the left subtree.
- Traverse the right subtree.
Algorithm For PostOrder Traversal:
- Traverse the left subtree.
- Traverse the right subtree.
- Print the node.


Algorithm:
- Take the first element of preorder traversal and increase the count.
- Find the index of the next element in the postorder traversal.
- All the elements to the left including this element will be in the left subtree and other elements in the right subtree.
- Recursively call for the right subtree too.
- Repeat until array is traversed.
Code:
#include<bits/stdc++.h>
using namespace std;
class Tree {
public:
int data;
Tree* left = NULL,*right = NULL;
// Constructor initialised
Tree(int x) {
data = x;
left = NULL;
right = NULL;
}
};
int search(int postorder[],int start,int end,int element) {
for (int i = start; i <= end;i++) {
// Check whether same or not
if (postorder[i] == element) {
return i;
}
}
}
void print_postorder(Tree* root) {
if (root == NULL) return;
print_postorder(root -> left);
print_postorder(root -> right);
cout << root -> data << ” “;
}
Tree* build_tree(int preorder[],int postorder[],int presi,int preei,int postsi,int postei){
// this case occurs when a node has only one child
if (presi > preei) {
return NULL;
}
Tree* curr_node = new Tree(preorder[presi]);
int x = curr_node -> data;
if (presi == preei) // Return the current node
return curr_node;
int search_index = search(postorder, postsi, postei,preorder[presi + 1] );
//Number of elements in left subtree
int elements = search_index – postsi + 1;
// Recursively call left subtree
curr_node->left = build_tree(preorder, postorder, presi + 1, presi + elements,postsi, search_index);
// Recursively call right subtree
curr_node -> right = build_tree(preorder, postorder, presi + elements + 1, preei,search_index + 1, postei – 1);
return curr_node;
}
int main() {
int preorder[] = {10,20,40,60,70,50,30};
int postorder[] = {60,70,40,50,20,30,10};
Tree* root = build_tree(preorder, postorder, 0, 6,0,6);
cout << “Postorder traversal\n“;
print_postorder(root);
return 0;
}
Output:
Postorder traversal
60 70 40 50 20 30 10
Time Complexity To Build Tree using Preorder and Postorder
Time Complexity
O(n ^ 2) in worst case
Space Complexity
O(n)
Login/Signup to comment