Construct a binary tree from InOrder & PreOrder traversals

The binary tree could be constructed as below

  • A given pre-order traversal sequence is used to find the root node of the binary tree to be constructed.
    The root node is then used to find its own index in the given inorder traversal sequence. This is needed for constructing the left and the right sub-trees of the root node.
    • The first node in the pre-order traversal is the root node of the tree.
  • The given in-order traversal sequence is used 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 ]

Note : The order of processing the nodes is from the first to the last node in the given pre-order traversal to construct the root and the sub-trees.


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



Program to create a binary tree from a given pre-order and in-order tree traversal sequence.

from typing import List, Optional # for annotations

# pre_order_index = 0
class Node :

    def __init__ (self, val=0, left=None, right=None) :
        self.val = val
        self.left = left
        self.right = right

class Tree :

    def __init__ (self, in_order_seq : List[int], pre_order_seq : List[int]) :

        self.pre_order = pre_order_seq
        self.in_order = in_order_seq
        self.nodes = len(pre_order_seq)

        # Use a dictionary to find the index of a node in the inorder sequence
        self.map_in_order = {}
        for index in range(self.nodes) :
            self.map_in_order[in_order_seq[index]] = index

        # global pre_ordex_index 
        self.pre_order_index = 0

    # Recursively construct a binary tree from an in_order and pre_order sequence
    def Construct (self, start : int, end : int) -> Optional[Node] :

        # Check if all the nodes in the pre-order sequence are processed. i.e if end < start
        if (start > end) :
            return None

        root = Node (self.pre_order[self.pre_order_index])

        # Fetch the index of the root node in the in_order sequence
        # to get the range of nodes in the left and right subtrees.
        index = self.map_in_order[root.val]

        # Process the nodes from left to right
        self.pre_order_index += 1

        # Recursively construct left sub-tree
        root.left = self.Construct (start, index - 1)

        # Recursively construct right sub-tree
        root.right = self.Construct (index + 1, end)

        return root

# Recursive function for inorder traversal
def In_Order_Traversal (root : Node) :

    if (root) :
        In_Order_Traversal (root.left)
        print(root.val, end=' ')
        In_Order_Traversal (root.right)

# Recursive function for preorder traversal
def Pre_Order_Traversal (root : Node) :

    if (root) :
       print(root.val, end=' ')
       Pre_Order_Traversal (root.left)
       Pre_Order_Traversal (root.right)

# Construct a binary tree from inorder and preorder traversals.
def BuildTree (in_order_seq : List[int], pre_order_seq : List[int]) -> Optional[Node] :

    t = Tree (in_order_seq, pre_order_seq)
    nodes = len(pre_order_seq)

    return t.Construct (0, nodes-1)

def main() :

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

    pre_order = [ 10, 12, 44, 30, 50, 16 ]
    in_order = [ 44, 12, 10, 50, 30, 16 ]

    print("\nGiven in-order traversal : ", end=' ')
    for node in in_order :
        print(node, end=' ')

    print("\nGiven pre-order traversal : ", end=' ')
    for node in pre_order :
        print(node, end=' ')

    root = BuildTree (in_order, pre_order)

    print("\nIn-order traversal of the constructed tree : ", end=' ')
    In_Order_Traversal(root)

    print("\nPre-order traversal of the constructed tree : ", end=' ')
    Pre_Order_Traversal(root)

if __name__ == "__main__" :
    main()

Output

Given in-order traversal :  44 12 10 50 30 16 
Given pre-order traversal :  10 12 44 30 50 16 
In-order traversal of the constructed tree :  44 12 10 50 30 16 
Pre-order traversal of the constructed tree :  10 12 44 30 50 16
#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_) { }
};

class Tree {

    private:
    vector<int> in_order;
    vector<int> pre_order;
    int pre_order_index;
    unordered_map<int, int> map_in_order;

    public:
    Tree (vector<int> in_order_seq, vector<int> pre_order_seq) {

        in_order = in_order_seq;
        pre_order = pre_order_seq;
        pre_order_index = 0;

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

    // Recursively construct a binary tree from an in_order and pre_order sequence
    Node* Construct (int start, int end) {

        // Check if all the nodes in the pre-order sequence are processed. i.e if end < start
        if (start > end) {
            return nullptr;
        }

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

        // Process the nodes from left to right
        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_in_order[root->val];

        // Recursively construct the left sub-tree
        root->left  = Construct (start, index - 1);

        // Recursively construct the right sub-tree
        root->right = Construct (index + 1, end);

        return root;
    }
};

// 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 preorder traversal
void Pre_Order_Traversal (Node* root) {

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

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

    int nodes = pre_order_seq.size();

    Tree *t = new Tree(in_order_seq, pre_order_seq);

    return t->Construct (0, nodes-1);
}

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 in-order traversal : ";
    for (const auto& node : in_order) {
        cout << node << " ";
    } cout << endl;

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

    Node* root = Build (in_order, pre_order);

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

    cout << "\nPre-order traversal of the constructed tree : ";
    Pre_Order_Traversal(root);

    return 0;
}

Output

Given in-order traversal : 44 12 10 50 30 16 
Given pre-order traversal : 10 12 44 30 50 16 
In-order traversal of the constructed tree : 44 12 10 50 30 16 
Pre-order traversal of the constructed tree : 10 12 44 30 50 16
import java.util.List;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Arrays;

class Node {

    int val;
    Node left;
    Node right;

    Node () { }
    Node (int x) { this.val = x; }
    Node (int x, Node left_, Node right_) {
        val = x;
        left = left_;
        right = right_;
    }
};

class Tree {

    List<Integer> in_order;
    List<Integer> pre_order;
    HashMap<Integer, Integer> map_in_order;
    int pre_order_index;

    Tree (List<Integer> in_order_seq, List<Integer> pre_order_seq) {

        in_order = new ArrayList<Integer>(in_order_seq);
        pre_order = new ArrayList<Integer>(pre_order_seq);
        map_in_order = new HashMap<Integer, Integer>();
        pre_order_index = 0;

        // Use an unordered_map to find the index of a node in the inorder sequence
        for (int index = 0; index < pre_order_seq.size(); index++) {
            map_in_order.put(in_order_seq.get(index), index);
        }
    }

    // Recursively construct a binary tree from an in_order and pre_order sequence
    Node Construct (int start, int end) {

        // Check if all the nodes in the pre-order sequence are processed. i.e if end < start
        if (start > end) {
            return null;
        }

        Node root = new Node (pre_order.get(pre_order_index));

        // Process the nodes from right to left
        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_in_order.get(root.val);

        // Recursively construct the left sub-tree
        root.left  = Construct (start, index - 1);

        // Recursively construct the right sub-tree
        root.right = Construct (index + 1, end);

        return root;
    }

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

        if (root != null) {
            In_Order_Traversal (root.left);
            System.out.print (root.val + " ");
            In_Order_Traversal (root.right);
        }
    }

    // Recursive functioni for preorder traversal
    void Pre_Order_Traversal (Node root) {

        if (root != null) {
           System.out.print (root.val + " ");
           Pre_Order_Traversal (root.left);
           Pre_Order_Traversal (root.right);
        }
    }

    public static void main (String[] args) {

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

        List<Integer> pre_order_seq = Arrays.asList (10, 12, 44, 30, 50, 16);
        List<Integer> in_order_seq = Arrays.asList (44, 12, 10, 50, 30, 16);

        System.out.print ("Given in-order traversal : ");
        for (int node : in_order_seq) {
            System.out.print(node + " ");
        } System.out.println();

        System.out.print ("Given pre-order traversal : ");
        for (int node : pre_order_seq) {
            System.out.print(node + " ");
        } System.out.println();

        Tree t = new Tree (in_order_seq, pre_order_seq);
        Node root = t.Construct (0, pre_order_seq.size() - 1);

        System.out.print ("In-order traversal of the constructed tree : ");
        t.In_Order_Traversal(root);

        System.out.print ("\nPre-order traversal of the constructed tree : ");
        t.Pre_Order_Traversal(root);
    }
}

Output

Given in-order traversal : 44 12 10 50 30 16 
Given pre-order traversal : 10 12 44 30 50 16 
In-order traversal of the constructed tree : 44 12 10 50 30 16 
Pre-order traversal of the constructed tree : 10 12 44 30 50 16


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