Construct Tree From Given Postorder And Preorder Traversal In C++

January 22, 2021

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