Construct Tree from given Postorder and Inorder Traversals in C++

January 22, 2021

Construct Tree From Given Inorder and Postorder traversals in C++

There are three types of traversals in a tree: Inorder, Preorder and Postorder traversal. A tree can be formed with any two tree traversals in which one of them being the in order traversal.

Postorder Traversal: We first  move to the left subtree and then to the right subtree and finally print the node.

Inorder Traversal: We move to the left subtree, then print the node and move to the right subtree.

Constructing a Tree from given Postorder and Inorder Traversals in C++

Algorithm For InOrder Traversal:

  1. Traverse The Left subtree.
  2. Print the node.
  3. Traverse the right subtree.

Algorithm For PostOrder Traversal:

  1. Traverse the left subtree.
  2. Traverse the right subtree.
  3. Print the node.
How to create a tree using the given inorder and postorder

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 inorder[],int start,int end,int element) {
    for (int i = start; i < end;i++) {
        // Check whether same or not
        if (inorder[i] == element) {
            return i;
        }
    }
}
void printInorder(Tree* node) 
{ 
    if (node == NULL) 
        return; 
 
    // Call left subtree
    printInorder(node->left); 
 
    // Print data
    cout<<node->data<<” “; 
 
    // Call Right subtree
    printInorder(node->right); 
}
Tree* build_tree(int inorder[],int postorder[],int start,int end){
    static int index = end + 1;
    // Not possible
    if (start > end) return NULL;
    Tree* curr_node = new Tree(postorder[index–]);
    int x = curr_node -> data;
    if (start == end) // Return the current nod
        return curr_node; 
 
    int search_index = search(inorder, start, end,x ); 
    
    // Recursively call right subtree
    curr_node -> right = build_tree(inorder, postorder, search_index + 1, end); 
    // Recursively call left subtree
    curr_node->left = build_tree(inorder, postorder, start, search_index – 1); 
    
    
 
    return curr_node; 
}
int main() {
    int in[] = { 12, 25, 30, 37, 40, 50, 60, 62, 70, 75, 87}; 
    int post[] = {12, 30, 40, 37, 25, 60, 70, 62, 87, 75, 50 }; 
    Tree* root = build_tree(in, post, 0, 10); 
    cout << “Inorder traversal\n“; 
    printInorder(root); 
    return 0;
}

Output:

Inorder traversal
12 25 30 37 40 50 60 62 70 75 87

 

Time Complexity To Build Tree using Postorder and Inorder

Time Complexity

O(n ^ 2) in worst case

Space Complexity

O(n)