Construct a binary tree from an InOrder & PostOrder traversals

The binary tree could be constructed as below

  • A given post-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 last node in the post-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 last to the first node in the given post-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 Post-Order traversal. InOrder_PostOrder_Construct_BTree



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

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

Output

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

Output

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

Output

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



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