Construct a Binary Tree from Postorder and Inorder using hashing

Construct a Binary Tree from Postorder and Inorder using stack and set:

To solve the problem follow the below idea:

We can optimize the above solution using hashing. We store indexes of inorder traversal in a hash table. So that search can be done O(1) time If given that element in the tree is not repeated.

Follow the below steps to solve the problem:

We first find the last node in post[]. The last node is “1”, we know this value is the root as the root always appears at the end of postorder traversal.
we get the index of postorder[i], in inorder using the map to find the left and right subtrees of the root. Everything on the left of “1” in in[] is in the left subtree and everything on right is in the right subtree.
We recur the above process for the following two.
- Recur for in[] = {6, 3, 7} and post[] = {6, 7, 3} Make the created tree as right child of root.
- Recur for in[] = {4, 8, 2, 5} and post[] = {8, 4, 5, 2}. Make the created tree the left child of the root.

Below is the implementation of the above approach:

C++

/* C++ program to construct tree using inorder and
postorder traversals */
#include <bits/stdc++.h>
 
using namespace std;
 
/* A binary tree node has data, pointer to left
child and a pointer to right child */
struct Node {
    int data;
    Node *left, *right;
};
 
// Utility function to create a new node
Node* newNode(int data);
 
/* Recursive function to construct binary of size n
from Inorder traversal in[] and Postorder traversal
post[]. Initial values of inStrt and inEnd should
be 0 and n -1. The function doesn't do any error
checking for cases where inorder and postorder
do not form a tree */
Node* buildUtil(int in[], int post[], int inStrt, int inEnd,
                int* pIndex, unordered_map<int, int>& mp)
{
    // Base case
    if (inStrt > inEnd)
        return NULL;
 
    /* Pick current node from Postorder traversal
    using postIndex and decrement postIndex */
    int curr = post[*pIndex];
    Node* node = newNode(curr);
    (*pIndex)--;
 
    /* If this node has no children then return */
    if (inStrt == inEnd)
        return node;
 
    /* Else find the index of this node in Inorder
    traversal */
    int iIndex = mp[curr];
 
    /* Using index in Inorder traversal, construct
    left and right subtrees */
    node->right = buildUtil(in, post, iIndex + 1, inEnd,
                            pIndex, mp);
    node->left = buildUtil(in, post, inStrt, iIndex - 1,
                           pIndex, mp);
 
    return node;
}
 
// This function mainly creates an unordered_map, then
// calls buildTreeUtil()
struct Node* buildTree(int in[], int post[], int len)
{
    // Store indexes of all items so that we
    // we can quickly find later
    unordered_map<int, int> mp;
    for (int i = 0; i < len; i++)
        mp[in[i]] = i;
 
    int index = len - 1; // Index in postorder
    return buildUtil(in, post, 0, len - 1, &index, mp);
}
 
/* Helper function that allocates a new node */
Node* newNode(int data)
{
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
 
/* This function is here just to test */
void preOrder(Node* node)
{
    if (node == NULL)
        return;
    printf("%d ", node->data);
    preOrder(node->left);
    preOrder(node->right);
}
 
// Driver code
int main()
{
    int in[] = { 4, 8, 2, 5, 1, 6, 3, 7 };
    int post[] = { 8, 4, 5, 2, 6, 7, 3, 1 };
    int n = sizeof(in) / sizeof(in[0]);
 
    Node* root = buildTree(in, post, n);
 
    cout << "Preorder of the constructed tree : \n";
    preOrder(root);
 
    return 0;
}

Java

/* Java program to construct tree using inorder and
postorder traversals */
import java.util.*;
class GFG {
 
    /* A binary tree node has data, pointer to left
    child and a pointer to right child */
    static class Node {
        int data;
        Node left, right;
    };
 
    // Utility function to create a new node
    /* Helper function that allocates a new node */
    static Node newNode(int data)
    {
        Node node = new Node();
        node.data = data;
        node.left = node.right = null;
        return (node);
    }
 
    /* Recursive function to construct binary of size n
    from Inorder traversal in[] and Postorder traversal
    post[]. Initial values of inStrt and inEnd should
    be 0 and n -1. The function doesn't do any error
    checking for cases where inorder and postorder
    do not form a tree */
    static Node buildUtil(int in[], int post[], int inStrt,
                          int inEnd)
    {
 
        // Base case
        if (inStrt > inEnd)
            return null;
 
        /* Pick current node from Postorder traversal
        using postIndex and decrement postIndex */
        int curr = post[index];
        Node node = newNode(curr);
        (index)--;
 
        /* If this node has no children then return */
        if (inStrt == inEnd)
            return node;
 
        /* Else find the index of this node in Inorder
        traversal */
        int iIndex = mp.get(curr);
 
        /* Using index in Inorder traversal, con
        left and right subtrees */
        node.right = buildUtil(in, post, iIndex + 1, inEnd);
        node.left = buildUtil(in, post, inStrt, iIndex - 1);
        return node;
    }
    static HashMap<Integer, Integer> mp
        = new HashMap<Integer, Integer>();
    static int index;
 
    // This function mainly creates an unordered_map, then
    // calls buildTreeUtil()
    static Node buildTree(int in[], int post[], int len)
    {
 
        // Store indexes of all items so that we
        // we can quickly find later
        for (int i = 0; i < len; i++)
            mp.put(in[i], i);
 
        index = len - 1; // Index in postorder
        return buildUtil(in, post, 0, len - 1);
    }
 
    /* This function is here just to test */
    static void preOrder(Node node)
    {
        if (node == null)
            return;
        System.out.printf("%d ", node.data);
        preOrder(node.left);
        preOrder(node.right);
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int in[] = { 4, 8, 2, 5, 1, 6, 3, 7 };
        int post[] = { 8, 4, 5, 2, 6, 7, 3, 1 };
        int n = in.length;
        Node root = buildTree(in, post, n);
        System.out.print(
            "Preorder of the constructed tree : \n");
        preOrder(root);
    }
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 program to construct tree using inorder
# and postorder traversals
 
# A binary tree node has data, pointer to left
# child and a pointer to right child
 
 
class Node:
 
    def __init__(self, x):
 
        self.data = x
        self.left = None
        self.right = None
 
# Recursive function to construct binary of size n
# from Inorder traversal in[] and Postorder traversal
# post[]. Initial values of inStrt and inEnd should
# be 0 and n -1. The function doesn't do any error
# checking for cases where inorder and postorder
# do not form a tree
 
 
def buildUtil(inn, post, innStrt, innEnd):
 
    global mp, index
 
    # Base case
    if (innStrt > innEnd):
        return None
 
    # Pick current node from Postorder traversal
    # using postIndex and decrement postIndex
    curr = post[index]
    node = Node(curr)
    index -= 1
 
    # If this node has no children then return
    if (innStrt == innEnd):
        return node
 
    # Else find the index of this node inn
    # Inorder traversal
    iIndex = mp[curr]
 
    # Using index in Inorder traversal,
    # construct left and right subtrees
    node.right = buildUtil(inn, post,
                           iIndex + 1, innEnd)
    node.left = buildUtil(inn, post, innStrt,
                          iIndex - 1)
 
    return node
 
# This function mainly creates an unordered_map,
# then calls buildTreeUtil()
 
 
def buildTree(inn, post, lenn):
 
    global index
 
    # Store indexes of all items so that we
    # we can quickly find later
    for i in range(lenn):
        mp[inn[i]] = i
 
    # Index in postorder
    index = lenn - 1
    return buildUtil(inn, post, 0, lenn - 1)
 
# This function is here just to test
 
 
def preOrder(node):
 
    if (node == None):
        return
 
    print(node.data, end=" ")
    preOrder(node.left)
    preOrder(node.right)
 
 
# Driver Code
if __name__ == '__main__':
 
    inn = [4, 8, 2, 5, 1, 6, 3, 7]
    post = [8, 4, 5, 2, 6, 7, 3, 1]
    n = len(inn)
    mp, index = {}, 0
 
    root = buildTree(inn, post, n)
 
    print("Preorder of the constructed tree :")
    preOrder(root)
 
# This code is contributed by mohit kumar 29

C#

/* C# program to construct tree using inorder and
postorder traversals */
using System;
using System.Collections.Generic;
class GFG {
 
    /* A binary tree node has data, pointer to left
  child and a pointer to right child */
    public
 
        class Node {
        public
 
            int data;
        public
 
            Node left,
            right;
    };
 
    // Utility function to create a new node
    /* Helper function that allocates a new node */
    static Node newNode(int data)
    {
        Node node = new Node();
        node.data = data;
        node.left = node.right = null;
        return (node);
    }
 
    /* Recursive function to construct binary of size n
  from Inorder traversal in[] and Postorder traversal
  post[]. Initial values of inStrt and inEnd should
  be 0 and n -1. The function doesn't do any error
  checking for cases where inorder and postorder
  do not form a tree */
    static Node buildUtil(int[] init, int[] post,
                          int inStrt, int inEnd)
    {
 
        // Base case
        if (inStrt > inEnd)
            return null;
 
        /* Pick current node from Postorder traversal
        using postIndex and decrement postIndex */
        int curr = post[index];
        Node node = newNode(curr);
        (index)--;
 
        /* If this node has no children then return */
        if (inStrt == inEnd)
            return node;
 
        /* Else find the index of this node in Inorder
        traversal */
        int iIndex = mp[curr];
 
        /* Using index in Inorder traversal, con
        left and right subtrees */
        node.right
            = buildUtil(init, post, iIndex + 1, inEnd);
        node.left
            = buildUtil(init, post, inStrt, iIndex - 1);
        return node;
    }
    static Dictionary<int, int> mp
        = new Dictionary<int, int>();
    static int index;
 
    // This function mainly creates an unordered_map, then
    // calls buildTreeUtil()
    static Node buildTree(int[] init, int[] post, int len)
    {
 
        // Store indexes of all items so that we
        // we can quickly find later
        for (int i = 0; i < len; i++)
            mp.Add(init[i], i);
 
        index = len - 1; // Index in postorder
        return buildUtil(init, post, 0, len - 1);
    }
 
    /* This function is here just to test */
    static void preOrder(Node node)
    {
        if (node == null)
            return;
        Console.Write(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int[] init = { 4, 8, 2, 5, 1, 6, 3, 7 };
        int[] post = { 8, 4, 5, 2, 6, 7, 3, 1 };
        int n = init.Length;
        Node root = buildTree(init, post, n);
        Console.Write(
            "Preorder of the constructed tree : \n");
        preOrder(root);
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
      /* JavaScript program to construct tree using inorder and
      postorder traversals */
      /* A binary tree node has data, pointer to left
      child and a pointer to right child */
      class Node {
        constructor() {
          this.data = 0;
          this.left = null;
          this.right = null;
        }
      }
 
      // Utility function to create a new node
      /* Helper function that allocates a new node */
      function newNode(data) {
        var node = new Node();
        node.data = data;
        node.left = node.right = null;
        return node;
      }
 
      /* Recursive function to construct binary of size n
      from Inorder traversal in[] and Postorder traversal
      post[]. Initial values of inStrt and inEnd should
      be 0 and n -1. The function doesn't do any error
      checking for cases where inorder and postorder
      do not form a tree */
      function buildUtil(init, post, inStrt, inEnd) {
        // Base case
        if (inStrt > inEnd) {
          return null;
        }
 
        /* Pick current node from Postorder traversal
          using postIndex and decrement postIndex */
        var curr = post[index];
        var node = newNode(curr);
        index--;
 
        /* If this node has no children then return */
        if (inStrt == inEnd) {
          return node;
        }
 
        /* Else find the index of this node in Inorder
          traversal */
        var iIndex = mp[curr];
 
        /* Using index in Inorder traversal, con
          left and right subtrees */
        node.right = buildUtil(init, post, iIndex + 1, inEnd);
        node.left = buildUtil(init, post, inStrt, iIndex - 1);
        return node;
      }
      var mp = {};
      var index;
 
      // This function mainly creates an unordered_map, then
      // calls buildTreeUtil()
      function buildTree(init, post, len) {
        // Store indexes of all items so that we
        // we can quickly find later
        for (var i = 0; i < len; i++) {
          mp[init[i]] = i;
        }
 
        index = len - 1; // Index in postorder
        return buildUtil(init, post, 0, len - 1);
      }
 
      /* This function is here just to test */
      function preOrder(node) {
        if (node == null) {
          return;
        }
        document.write(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
      }
 
      // Driver code
      var init = [4, 8, 2, 5, 1, 6, 3, 7];
      var post = [8, 4, 5, 2, 6, 7, 3, 1];
      var n = init.length;
      var root = buildTree(init, post, n);
      document.write("Preorder of the constructed tree : <br>");
      preOrder(root);
       
</script>

Output

Preorder of the constructed tree : 
1 2 4 8 5 3 6 7

Time Complexity: O(N)
Auxiliary Space: O(N), The extra space is used due to the recursion call stack and to store the elements in the map.

Construct a Binary Tree from Postorder and Inorder

Given Postorder and Inorder traversals, construct the tree.

Examples:

Input:
in[] = {2, 1, 3}
post[] = {2, 3, 1}

Output: Root of below tree

1
/ \
2 3

Input:
in[] = {4, 8, 2, 5, 1, 6, 3, 7}
post[] = {8, 4, 5, 2, 6, 7, 3, 1}

Output: Root of below tree

1
/ \
2 3
/ \ / \
4 5 6 7
\
8

Approach: To solve the problem follow the below idea:

Note: We have already discussed the construction of trees from Inorder and Preorder traversals:

Follow the below steps:

Let us see the process of constructing a tree from in[] = {4, 8, 2, 5, 1, 6, 3, 7} and post[] = {8, 4, 5, 2, 6, 7, 3, 1}:

We first find the last node in post[]. The last node is “1”, we know this value is the root as the root always appears at the end of postorder traversal.
We search “1” in in[] to find the left and right subtrees of the root. Everything on the left of “1” in in[] is in the left subtree and everything on right is in the right subtree.

1
/ \
[4, 8, 2, 5] [6, 3, 7]

We recur the above process for the following two.
- Recur for in[] = {6, 3, 7} and post[] = {6, 7, 3} Make the created tree as right child of root.
- Recur for in[] = {4, 8, 2, 5} and post[] = {8, 4, 5, 2}. Make the created tree the left child of the root.

Note: One important observation is, that we recursively call for the right subtree before the left subtree as we decrease the index of the postorder index whenever we create a new node

Below is the implementation of the above approach:

C++

/* C++ program to construct tree using inorder and
   postorder traversals */
#include <bits/stdc++.h>
 
using namespace std;
 
/* A binary tree node has data, pointer to left
   child and a pointer to right child */
struct Node {
    int data;
    Node *left, *right;
};
 
// Utility function to create a new node
Node* newNode(int data);
 
/* Prototypes for utility functions */
int search(int arr[], int strt, int end, int value);
 
/* Recursive function to construct binary of size n
   from  Inorder traversal in[] and Postorder traversal
   post[].  Initial values of inStrt and inEnd should
   be 0 and n -1.  The function doesn't do any error
   checking for cases where inorder and postorder
   do not form a tree */
Node* buildUtil(int in[], int post[], int inStrt, int inEnd,
                int* pIndex)
{
    // Base case
    if (inStrt > inEnd)
        return NULL;
 
    /* Pick current node from Postorder traversal using
       postIndex and decrement postIndex */
    Node* node = newNode(post[*pIndex]);
    (*pIndex)--;
 
    /* If this node has no children then return */
    if (inStrt == inEnd)
        return node;
 
    /* Else find the index of this node in Inorder
       traversal */
    int iIndex = search(in, inStrt, inEnd, node->data);
 
    /* Using index in Inorder traversal, construct left and
       right subtrees */
    node->right
        = buildUtil(in, post, iIndex + 1, inEnd, pIndex);
    node->left
        = buildUtil(in, post, inStrt, iIndex - 1, pIndex);
 
    return node;
}
 
// This function mainly initializes index of root
// and calls buildUtil()
Node* buildTree(int in[], int post[], int n)
{
    int pIndex = n - 1;
    return buildUtil(in, post, 0, n - 1, &pIndex);
}
 
/* Function to find index of value in arr[start...end]
   The function assumes that value is postsent in in[] */
int search(int arr[], int strt, int end, int value)
{
    int i;
    for (i = strt; i <= end; i++) {
        if (arr[i] == value)
            break;
    }
    return i;
}
 
/* Helper function that allocates a new node */
Node* newNode(int data)
{
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
 
/* This function is here just to test  */
void preOrder(Node* node)
{
    if (node == NULL)
        return;
    printf("%d ", node->data);
    preOrder(node->left);
    preOrder(node->right);
}
 
// Driver code
int main()
{
    int in[] = { 4, 8, 2, 5, 1, 6, 3, 7 };
    int post[] = { 8, 4, 5, 2, 6, 7, 3, 1 };
    int n = sizeof(in) / sizeof(in[0]);
 
    Node* root = buildTree(in, post, n);
 
    cout << "Preorder of the constructed tree : \n";
    preOrder(root);
 
    return 0;
}

Java

// Java program to construct a tree using inorder
// and postorder traversals
 
/* A binary tree node has data, pointer to left
   child and a pointer to right child */
class Node {
    int data;
    Node left, right;
 
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
class BinaryTree {
    /* Recursive function to construct binary of size n
       from  Inorder traversal in[] and Postorder traversal
       post[]. Initial values of inStrt and inEnd should
       be 0 and n -1.  The function doesn't do any error
       checking for cases where inorder and postorder
       do not form a tree */
    Node buildUtil(int in[], int post[], int inStrt,
                   int inEnd, int postStrt, int postEnd)
    {
        // Base case
        if (inStrt > inEnd)
            return null;
 
        /* Pick current node from Postorder traversal using
           postIndex and decrement postIndex */
        Node node = new Node(post[postEnd]);
 
        /* If this node has no children then return */
        if (inStrt == inEnd)
            return node;
        int iIndex = search(in, inStrt, inEnd, node.data);
 
        /* Using index in Inorder traversal, construct left
           and right subtrees */
        node.left = buildUtil(
            in, post, inStrt, iIndex - 1, postStrt,
            postStrt - inStrt + iIndex - 1);
        node.right = buildUtil(in, post, iIndex + 1, inEnd,
                               postEnd - inEnd + iIndex,
                               postEnd - 1);
 
        return node;
    }
 
    /* Function to find index of value in arr[start...end]
       The function assumes that value is postsent in in[]
     */
    int search(int arr[], int strt, int end, int value)
    {
        int i;
        for (i = strt; i <= end; i++) {
            if (arr[i] == value)
                break;
        }
        return i;
    }
 
    /* This function is here just to test  */
    void preOrder(Node node)
    {
        if (node == null)
            return;
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        int in[] = new int[] { 4, 8, 2, 5, 1, 6, 3, 7 };
        int post[] = new int[] { 8, 4, 5, 2, 6, 7, 3, 1 };
        int n = in.length;
        Node root
            = tree.buildUtil(in, post, 0, n - 1, 0, n - 1);
        System.out.println(
            "Preorder of the constructed tree : ");
        tree.preOrder(root);
    }
}
 
// This code has been contributed by Mayank
// Jaiswal(mayank_24)

Python3

# Python3 program to construct tree using
# inorder and postorder traversals
 
# Helper function that allocates
# a new node
 
 
class newNode:
    def __init__(self, data):
        self.data = data
        self.left = self.right = None
 
# Recursive function to construct binary
# of size n from Inorder traversal in[]
# and Postorder traversal post[]. Initial
# values of inStrt and inEnd should be
# 0 and n -1. The function doesn't do any
# error checking for cases where inorder
# and postorder do not form a tree
 
 
def buildUtil(In, post, inStrt, inEnd, pIndex):
 
    # Base case
    if (inStrt > inEnd):
        return None
 
    # Pick current node from Postorder traversal
    # using postIndex and decrement postIndex
    node = newNode(post[pIndex[0]])
    pIndex[0] -= 1
 
    # If this node has no children
    # then return
    if (inStrt == inEnd):
        return node
 
    # Else find the index of this node
    # in Inorder traversal
    iIndex = search(In, inStrt, inEnd, node.data)
 
    # Using index in Inorder traversal,
    # construct left and right subtress
    node.right = buildUtil(In, post, iIndex + 1,
                           inEnd, pIndex)
    node.left = buildUtil(In, post, inStrt,
                          iIndex - 1, pIndex)
 
    return node
 
# This function mainly initializes index
# of root and calls buildUtil()
 
 
def buildTree(In, post, n):
    pIndex = [n - 1]
    return buildUtil(In, post, 0, n - 1, pIndex)
 
# Function to find index of value in
# arr[start...end]. The function assumes
# that value is postsent in in[]
 
 
def search(arr, strt, end, value):
    i = 0
    for i in range(strt, end + 1):
        if (arr[i] == value):
            break
    return i
 
# This function is here just to test
 
 
def preOrder(node):
    if node == None:
        return
    print(node.data, end=" ")
    preOrder(node.left)
    preOrder(node.right)
 
 
# Driver code
if __name__ == '__main__':
    In = [4, 8, 2, 5, 1, 6, 3, 7]
    post = [8, 4, 5, 2, 6, 7, 3, 1]
    n = len(In)
 
    root = buildTree(In, post, n)
 
    print("Preorder of the constructed tree :")
    preOrder(root)
 
# This code is contributed by PranchalK

C#

// C# program to construct a tree using
// inorder and postorder traversals
using System;
 
/* A binary tree node has data, pointer
to left child and a pointer to right child */
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int data)
    {
        this.data = data;
        left = right = null;
    }
}
 
// Class Index created to implement
// pass by reference of Index
public class Index {
    public int index;
}
 
class GFG {
    /* Recursive function to construct binary
    of size n from Inorder traversal in[] and
    Postorder traversal post[]. Initial values
    of inStrt and inEnd should be 0 and n -1.
    The function doesn't do any error checking
    for cases where inorder and postorder do
    not form a tree */
    public virtual Node buildUtil(int[] @in, int[] post,
                                  int inStrt, int inEnd,
                                  Index pIndex)
    {
        // Base case
        if (inStrt > inEnd) {
            return null;
        }
 
        /* Pick current node from Postorder traversal
        using postIndex and decrement postIndex */
        Node node = new Node(post[pIndex.index]);
        (pIndex.index)--;
 
        /* If this node has no children
        then return */
        if (inStrt == inEnd) {
            return node;
        }
 
        /* Else find the index of this node
        in Inorder traversal */
        int iIndex = search(@in, inStrt, inEnd, node.data);
 
        /* Using index in Inorder traversal,
        construct left and right subtrees */
        node.right = buildUtil(@in, post, iIndex + 1, inEnd,
                               pIndex);
        node.left = buildUtil(@in, post, inStrt, iIndex - 1,
                              pIndex);
 
        return node;
    }
 
    // This function mainly initializes
    // index of root and calls buildUtil()
    public virtual Node buildTree(int[] @in, int[] post,
                                  int n)
    {
        Index pIndex = new Index();
        pIndex.index = n - 1;
        return buildUtil(@in, post, 0, n - 1, pIndex);
    }
 
    /* Function to find index of value in
    arr[start...end]. The function assumes
    that value is postsent in in[] */
    public virtual int search(int[] arr, int strt, int end,
                              int value)
    {
        int i;
        for (i = strt; i <= end; i++) {
            if (arr[i] == value) {
                break;
            }
        }
        return i;
    }
 
    /* This function is here just to test */
    public virtual void preOrder(Node node)
    {
        if (node == null) {
            return;
        }
        Console.Write(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        GFG tree = new GFG();
        int[] @in = new int[] { 4, 8, 2, 5, 1, 6, 3, 7 };
        int[] post = new int[] { 8, 4, 5, 2, 6, 7, 3, 1 };
        int n = @in.Length;
        Node root = tree.buildTree(@in, post, n);
        Console.WriteLine(
            "Preorder of the constructed tree : ");
        tree.preOrder(root);
    }
}
 
// This code is contributed by Shrikant13

Javascript

<script>
// Javascript program to construct a tree using inorder
// and postorder traversals
     
    /* A binary tree node has data, pointer to left
   child and a pointer to right child */
    class Node
    {
        constructor(data)
        {
            this.data = data;
            this.left = this.right = null;
        }
    }
     
    /* Recursive function to construct binary of size n
       from  Inorder traversal in[] and Postorder traversal
       post[]. Initial values of inStrt and inEnd should
       be 0 and n -1.  The function doesn't do any error
       checking for cases where inorder and postorder
       do not form a tree */
    function buildUtil(In, post, inStrt, inEnd, postStrt, postEnd)
    {
     
        // Base case
        if (inStrt > inEnd)
            return null;
  
        /* Pick current node from Postorder traversal using
           postIndex and decrement postIndex */
        let node = new Node(post[postEnd]);
  
        /* If this node has no children then return */
        if (inStrt == inEnd)
            return node;
        let iIndex = search(In, inStrt, inEnd, node.data);
  
        /* Using index in Inorder traversal, construct left
           and right subtrees */
        node.left = buildUtil(
            In, post, inStrt, iIndex - 1, postStrt,
            postStrt - inStrt + iIndex - 1);
        node.right = buildUtil(In, post, iIndex + 1, inEnd,
                               postEnd - inEnd + iIndex,
                               postEnd - 1);
  
        return node;
    }
     
    /* Function to find index of value in arr[start...end]
       The function assumes that value is postsent in in[]
     */
    function search(arr,strt,end,value)
    {
        let i;
        for (i = strt; i <= end; i++) {
            if (arr[i] == value)
                break;
        }
        return i;
    }
     
    /* This function is here just to test  */
    function preOrder(node)
    {
        if (node == null)
            return;
        document.write(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }
     
    // Driver Code
    let In=[4, 8, 2, 5, 1, 6, 3, 7];
    let post=[8, 4, 5, 2, 6, 7, 3, 1];
    let n = In.length;
    let root
            = buildUtil(In, post, 0, n - 1, 0, n - 1);
    document.write(
            "Preorder of the constructed tree : <br>");
    preOrder(root);
     
    // This code is contributed by unknown2108
</script>

Output

Preorder of the constructed tree : 
1 2 4 8 5 3 6 7

Time Complexity: O(N²), Where N is the length of the given inorder array
Auxiliary Space: O(N), for recursive call stack

Tags:

#Adobe #Amazon #cpp-unordered_map #DSA #Hash #Tree #Adobe #Amazon #Hash #Tree

Construct a Binary Tree from Postorder and Inorder using stack and set:

Construct a Binary Tree from Postorder and Inorder using hashing

C++

Java

Python3

C#

Javascript

Construct a Binary Tree from Postorder and Inorder

C++

Java

Python3

C#

Javascript

Similar Reads