Construct a binary tree from InOrder & PostOrder traversals

The binary tree could be constructed as below

  • Post-Order traversal is used to find the root of the tree / subtrees in the binary tree. The root node is then used to find its own index in the inorder traversal.
    • The last node in the post-order traversal is the root node of the tree.
  • In-Order traversal traversal is to find the range of nodes that are in the left sub-tree and the right sub-tree.
    • The left sub-tree will have the nodes in the range [ start, index - 1 ]
    • The right sub-tree will have the nodes in the range [ index + 1, end ]

Consider the below example in which a binary tree is constructed using the given In-Order and Post-Order traversal. InOrder_PostOrder_Construct_BTree



C++ : Program to create a binary tree from a given in-order and post-order tree traversal sequence.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Node {

    public:

    int val;

    Node *left;

    Node *right;

    Node() : val(0), left(nullptr), right(nullptr) { }

    Node(int x) : val(x), left(nullptr), right(nullptr) { }

    Node(int x, Node *left_, Node *right_) : val(x), left(left_), right(right_) { }
};

// Recursive function for inorder traversal
void In_Order_Traversal (Node* root) {

    if (root != nullptr) {
        In_Order_Traversal (root->left);
        cout << root->val << ' ';
        In_Order_Traversal (root->right);
    }
}

// Recursive functioni for postorder traversal
void Post_Order_Traversal (Node* root) {

    if (root != nullptr) {
       Post_Order_Traversal (root->left);
       Post_Order_Traversal (root->right);
       cout << root->val << ' ';
    }
}

// Recursively construct a binary tree from an in_order and post_order sequence
Node* Construct_Tree (int start, int end, const vector<int>& post_order_seq, int& post_order_index,
                      unordered_map<int, int>& map_in_order) {

    // Nodes exhausted.
    if (start > end) {
        return nullptr;
    }

    Node* root = new Node (post_order_seq[post_order_index]);

    /* Note : The previous node in the post_order sequence will be the root node 
              of the right-subtree that would created using the in_order sequence from (start, end) */
    post_order_index -= 1;

    // Fetch the index of the root node in the in_order sequence to get the range of the left and right subtree nodes.
    int index = map_in_order[root->val];

    // Recursively construct right sub-tree
    root->right = Construct_Tree (index + 1, end, post_order_seq, post_order_index, map_in_order);

    // Recursively construct left sub-tree
    root->left  = Construct_Tree (start, index - 1, post_order_seq, post_order_index, map_in_order);

    return root;
}

// Construct a binary tree from inorder and preorder traversals.
Node* Get_Root (const vector<int>& in_order_seq, const vector<int>& post_order_seq) {

    int nodes = post_order_seq.size();

    // Use an unordered_map to find the index of a node in the inorder sequence
    unordered_map<int, int> map_in_order;
    for (int index = 0; index < nodes; index++) {
        map_in_order[in_order_seq[index]] = index;
    }

    int post_order_index = nodes-1;

    return Construct_Tree (0, nodes-1, post_order_seq, post_order_index, map_in_order);
}

int main() {

    /* Construct the following tree
               10
              /  \
             12   30
            /    /  \
           44   50   16
    */

    vector<int> post_order = { 44, 12, 50, 16, 30, 10 };
    vector<int> in_order = { 44, 12, 10, 50, 30, 16 };

    cout << "Given post-order traversal : ";
    for (const auto& node : post_order) {
        cout << node << " ";
    } cout << endl;

    cout << "Given in-order traversal : ";
    for (const auto& node : in_order) {
        cout << node << " ";
    } cout << endl;

    Node* root = Get_Root(in_order, post_order);

    cout << "\nPost-order traversal of constructed tree : ";
    Post_Order_Traversal(root);

    cout << endl;

    cout << "In-order traversal of constructed tree : ";
    In_Order_Traversal(root);

    return 0;
}

Output

Given post-order traversal : 44 12 50 16 30 10 
Given in-order traversal : 44 12 10 50 30 16 

Post-order traversal of constructed tree : 44 12 50 16 30 10 
In-order traversal of constructed tree : 44 12 10 50 30 16


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.