Construct a binary tree from InOrder & PreOrder traversals

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()

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;
}

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 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.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);
    }
}

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