Construct a binary tree from an InOrder & PostOrder traversals

from typing import List, Optional # for annotations

# post_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], post_order_seq : List[int]) :

        self.post_order = post_order_seq
        self.in_order = in_order_seq
        self.nodes = len(post_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 post_ordex_index 
        self.post_order_index = self.nodes - 1

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

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

        root = Node (self.post_order[self.post_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 right to left
        self.post_order_index -= 1

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

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

        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 postorder traversal
def Post_Order_Traversal (root : Node) :

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

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

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

    return t.Construct (0, nodes-1)

def main() :

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

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

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

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

    root = BuildTree (in_order, post_order)

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

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

if __name__ == "__main__" :
    main()

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

#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> post_order;
    int post_order_index;
    unordered_map<int, int> map_in_order;

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

        in_order = in_order_seq;
        post_order = post_order_seq;
        post_order_index = post_order_seq.size() - 1;

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

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

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

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

        // Process the nodes from right to left
        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 the right sub-tree
        root->right = Construct (index + 1, end);

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

        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 postorder traversal
void Post_Order_Traversal (Node* root) {

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

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

    int nodes = post_order_seq.size();

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

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

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

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

    Node* root = Build (in_order, post_order);

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

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

    return 0;
}

Given in-order traversal : 44 12 10 50 30 16 
Given post-order traversal : 44 12 50 16 30 10 
In-order traversal of the constructed tree : 44 12 10 50 30 16 
Post-order traversal of the constructed tree : 44 12 50 16 30 10```

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> post_order;
    HashMap<Integer, Integer> map_in_order;
    int post_order_index;

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

        in_order = new ArrayList<Integer>(in_order_seq);
        post_order = new ArrayList<Integer>(post_order_seq);
        map_in_order = new HashMap<Integer, Integer>();
        post_order_index = post_order_seq.size() - 1;

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

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

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

        Node root = new Node (post_order.get(post_order_index));

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

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

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

        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 postorder traversal
    void Post_Order_Traversal (Node root) {

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

    public static void main (String[] args) {

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

        List<Integer> post_order_seq = Arrays.asList (44, 12, 50, 16, 30, 10);
        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 post-order traversal : ");
        for (int node : post_order_seq) {
            System.out.print(node + " ");
        } System.out.println();

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

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

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

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