Construct a binary tree from InOrder & PreOrder traversals

The binary tree could be constructed as below

  • Pre-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 in-order traversal.
    • The first node in the pre-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 ]
  • As the left sub-tree and the right sub-tree is created using the nodes in the range [ start , index - 1 ] and [ index + 1, end ] respectively, the solution is recursive in nature.

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



C++ : Program to create a binary tree from a given pre-order and in-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 Inorder_Traversal (Node* root) {

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

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

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

// Recursively construct a binary tree from an in_order and pre_order sequence
Node* Construct_Tree (int start, int end, const vector<int>& pre_order_seq, int& pre_order_index, 
                      unordered_map<int, int>& map_inorder) {

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

    Node* root = new Node (pre_order_seq[pre_order_index]);

    /* Note : The next node in the pre_order sequence will be the root node 
              of subtree that would created using the in_order sequence from (start, end) */
    pre_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_inorder[root->val];

    // Recursively construct left sub-tree
    root->left  = Construct_Tree (start, index - 1, pre_order_seq, pre_order_index, map_inorder);

    // Recursively construct right sub-tree
    root->right = Construct_Tree (index + 1, end, pre_order_seq, pre_order_index, map_inorder);

    return root;
}

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

    int nodes = pre_order_seq.size();

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

    int pre_order_index = 0;

    return Construct_Tree (0, nodes-1, pre_order_seq, pre_order_index, map_inorder);
}

int main() {

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

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

    cout << "Given preorder traversal : ";
    for (const auto& node : pre_order) {
        cout << node << " ";
    } cout << endl;

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

    Node* root = Get_Root(pre_order, in_order);

    cout << "\nPreorder traversal of constructed tree : ";
    Preorder_Traversal(root);

    cout << endl;

    cout << "Inorder traversal of constructed tree : ";
    Inorder_Traversal(root);

    return 0;
}

Output

Given preorder traversal : 10 12 44 30 50 16 
Given inorder traversal : 44 12 10 50 30 16 

Preorder traversal of constructed tree : 10 12 44 30 50 16 
Inorder traversal of constructed tree : 44 12 10 50 30 16 


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