Open In App

Construct a Binary Tree from Postorder and Inorder

Last Updated : 23 Jul, 2025
Suggest changes
Share
Like Article
Like
Report

Given inorder and postorder traversals of a binary tree(having n nodes) in the arrays inorder[] and postorder[] respectively. The task is to construct a unique binary tree from these traversals and return the preorder traversal of the constructed tree.

Examples: 

Input: inorder[] = [2, 1, 3], postorder[] = [2, 3, 1]
Output: 1 2 3
Explanation: The below tree is constructed from the given inorder and postorder traversal.

Print-Nodes-in-Top-View-of-Binary-Tree-2


Input: inorder[] = [4, 2, 5, 1, 3], postorder[] = [4, 5, 2, 3, 1]
Output: 1 2 4 5 3
Explanation: The below tree is constructed from the given inorder and postorder traversal.

check-if-given-preorder-inorder-and-postorder-traversals-are-of-same-tree

Table of Content

[Naive approach] Search current element every time - O(n^2) Time and O(n) Space

The idea behind this algorithm is to construct a binary tree using the given inorder and postorder traversals. We start by recognizing that the last element of the postorder traversal represents the root of the tree. Using this value, we find its position in the inorder traversal, which allows us to divide the tree into left and right subtrees. We then recursively repeat this process, constructing the right subtree first and then the left subtree. Once the tree is fully constructed, we can perform a preorder traversal to print the elements in the desired order.

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.

C++ 
// C++ program to construct tree using inorder and // postorder traversals #include <bits/stdc++.h> using namespace std; class Node {  public:  int data;  Node *left, *right;  Node(int x) {  data = x;  left = right = nullptr;  } }; // Function to find index of value in arr[start...end] // The function assumes that value is present in in[] int search(vector<int> &arr, int strt, int end, int value) {  int i;  for (i = strt; i <= end; i++) {  if (arr[i] == value)  break;  }  return i; } // Recursive function to construct binary tree of size n // from Inorder traversal in[] and Postorder traversal // post[]. Initial values of inStrt and inEnd should // be 0 and n - 1. Node *buildUtil(vector<int> &inorder, vector<int> &postorder,   int inStrt, int inEnd, int &pIndex) {  // if inStart is greater than inEnd return nullptr  if (inStrt > inEnd)  return nullptr;  // Pick current node from Postorder traversal using  // postIndex and decrement postIndex  Node *node = new Node(postorder[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(inorder, inStrt, inEnd, node->data);  // Using index in Inorder traversal, construct left and  // right subtrees  node->right = buildUtil(inorder, postorder, iIndex + 1, inEnd, pIndex);  node->left = buildUtil(inorder, postorder, inStrt, iIndex - 1, pIndex);  return node; } // This function mainly initializes index of root // and calls buildUtil() Node *buildTree(vector<int> &inorder, vector<int> &postorder) {  int n = inorder.size();  int pIndex = n - 1;  return buildUtil(inorder, postorder, 0, n - 1, pIndex); } // Print the preorder traversal of a binary tree void print(Node *curr) {  if (curr == nullptr)  return;  cout << curr->data << " ";  print(curr->left);  print(curr->right); } int main() {  vector<int> inorder = {4, 8, 2, 5, 1, 6, 3, 7};  vector<int> postorder = {8, 4, 5, 2, 6, 7, 3, 1};  Node *root = buildTree(inorder, postorder);  print(root);  return 0; }
C 
// C program to construct tree using // inorder and postorder traversals #include <stdio.h> #include <stdlib.h> struct Node {  int data;  struct Node *left;  struct Node *right; }; struct Node *createNode(int x); // Function to find index of value in arr[start...end] // The function assumes that value is present in in[] int search(int arr[], int start, int end, int value) {  int i;  for (i = start; i <= end; i++) {  if (arr[i] == value)  break;  }  return i; } // Recursive function to construct binary tree of size n // from Inorder traversal in[] and Postorder traversal // post[]. struct Node *buildUtil(int inorder[], int postorder[],   int inStart, int inEnd, int *pIndex) {  if (inStart > inEnd)  return NULL;  // Pick current node from Postorder traversal using  // postIndex and decrement postIndex  struct Node *node = createNode(postorder[*pIndex]);  (*pIndex)--;  // If this node has no children then return  if (inStart == inEnd)  return node;  // Else find the index of this node in Inorder traversal  int inIndex = search(inorder, inStart, inEnd, node->data);  // Using index in Inorder traversal, construct left and  // right subtrees  node->right = buildUtil(inorder, postorder, inIndex + 1, inEnd, pIndex);  node->left = buildUtil(inorder, postorder, inStart, inIndex - 1, pIndex);  return node; } // This function mainly initializes index of root // and calls buildUtil() struct Node *buildTree(int inorder[], int postorder[], int n) {  int pIndex = n - 1;  return buildUtil(inorder, postorder, 0, n - 1, &pIndex); } // Print the preorder of a binary tree void printPreorder(struct Node *node) {  if (node == NULL)  return;  printf("%d ", node->data);  printPreorder(node->left);  printPreorder(node->right); } struct Node *createNode(int x) {  struct Node *node =   (struct Node *)malloc(sizeof(struct Node));  node->data = x;  node->left = NULL;  node->right = NULL;  return node; } int main() {  int inorder[] = {4, 8, 2, 5, 1, 6, 3, 7};  int postorder[] = {8, 4, 5, 2, 6, 7, 3, 1};  int n = sizeof(inorder) / sizeof(inorder[0]);  struct Node *root = buildTree(inorder, postorder, n);  printPreorder(root);  return 0; }
Java 
// Java program to construct tree using // inorder and postorder traversals import java.util.*; class Node {  int data;  Node left, right;  Node(int x) {  data = x;  left = right = null;  } } class GfG {  // Function to find index of value in arr[start...end]  // The function assumes that value is present in in[]  static int search(List<Integer> arr, int strt, int end,  int value) {  int i;  for (i = strt; i <= end; i++) {  if (arr.get(i) == value)  break;  }  return i;  }  // 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.  static Node buildUtil(List<Integer> in,  List<Integer> post, int inStrt,  int inEnd, int[] pIndex) {  if (inStrt > inEnd)  return null;  // Pick current node from Postorder traversal using  // postIndex and decrement postIndex  Node node = new Node(post.get(pIndex[0]));  pIndex[0]--;  // 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()  static Node buildTree(List<Integer> in,  List<Integer> post) {  int n = in.size();  int[] pIndex = { n - 1 };  return buildUtil(in, post, 0, n - 1, pIndex);  }  // Print the preorder of a binary tree  static void print(Node curr) {  if (curr == null)  return;  System.out.print(curr.data + " ");  print(curr.left);  print(curr.right);  }  public static void main(String[] args) {  List<Integer> in  = Arrays.asList(4, 8, 2, 5, 1, 6, 3, 7);  List<Integer> post  = Arrays.asList(8, 4, 5, 2, 6, 7, 3, 1);  Node root = buildTree(in, post);  print(root);  } }
Python 
# Python program to construct tree using  # inorder and postorder traversals class Node: def __init__(self, x): self.data = x self.left = None self.right = None # Function to find index of value in arr[start...end] # The function assumes that value is present in in[] def search(arr, start, end, value): for i in range(start, end + 1): if arr[i] == value: return i return -1 # Recursive function to construct binary tree of size n # from Inorder traversal in[] and Postorder traversal # post[]. Initial values of inStrt and inEnd should # be 0 and n - 1. def build_util(inorder, postorder, in_start, in_end, post_index): if in_start > in_end: return None # Pick current node from Postorder traversal using # postIndex and decrement postIndex node = Node(postorder[post_index[0]]) post_index[0] -= 1 # If this node has no children then return if in_start == in_end: return node # Else find the index of this node in Inorder traversal in_index = search(inorder, in_start, in_end, node.data) # Using index in Inorder traversal, construct left and # right subtrees node.right = build_util(inorder, postorder, in_index + 1, in_end, post_index) node.left = build_util(inorder, postorder, in_start, in_index - 1, post_index) return node # This function mainly initializes index of root # and calls buildUtil() def buildTree(inorder, postorder): n = len(inorder) post_index = [n - 1] return build_util(inorder, postorder, 0, n - 1, post_index) # Print the preorder of a binary tree def print_preorder(node): if node is None: return print(node.data, end=" ") print_preorder(node.left) print_preorder(node.right) if __name__ == "__main__": inorder = [4, 8, 2, 5, 1, 6, 3, 7] postorder = [8, 4, 5, 2, 6, 7, 3, 1] root = buildTree(inorder, postorder) print_preorder(root)
C# 
// C# program to construct tree using // inorder and postorder traversals using System; using System.Collections.Generic; class Node {  public int data;  public Node left, right;    public Node(int x) {  data = x;  left = right = null;  } } class GfG {  // Function to find index of value in arr[start...end]  // The function assumes that value is present in in[]  static int Search(List<int> arr, int start, int end, int value) {  int i;  for (i = start; i <= end; i++) {  if (arr[i] == value)  break;  }  return i;  }  // 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.  static Node BuildUtil(List<int> inorder, List<int> postorder,   int inStart, int inEnd, ref int pIndex) {  if (inStart > inEnd)  return null;  // Pick current node from Postorder traversal using  // postIndex and decrement postIndex  Node node = new Node(postorder[pIndex]);  pIndex--;  // If this node has no children then return  if (inStart == inEnd)  return node;  // Else find the index of this node in Inorder traversal  int inIndex = Search(inorder, inStart, inEnd, node.data);  // Using index in Inorder traversal, construct left and  // right subtrees  node.right = BuildUtil(inorder, postorder,  inIndex + 1, inEnd, ref pIndex);  node.left = BuildUtil(inorder, postorder,   inStart, inIndex - 1, ref pIndex);  return node;  }  // This function mainly initializes index of root  // and calls BuildUtil()  static Node buildTree(List<int> inorder, List<int> postorder) {  int n = inorder.Count;  int pIndex = n - 1;  return BuildUtil(inorder, postorder, 0, n - 1, ref pIndex);  }  // Print the preorder of a binary tree  static void Print(Node curr) {  if (curr == null)  return;  Console.Write(curr.data + " ");  Print(curr.left);  Print(curr.right);  }  static void Main() {  List<int> inorder = new List<int> { 4, 8, 2, 5, 1, 6, 3, 7 };  List<int> postorder = new List<int> { 8, 4, 5, 2, 6, 7, 3, 1 };  Node root = buildTree(inorder, postorder);  Print(root);  } }
JavaScript 
// JavaScript program to construct tree using // inorder and postorder traversals class Node {  constructor(x) {  this.data = x;  this.left = null;  this.right = null;  } } // Function to find index of value in arr[start...end] // The function assumes that value is present in in[] function search(arr, start, end, value) {  for (let i = start; i <= end; i++) {  if (arr[i] === value)  return i;  }  return -1; } // 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. function buildUtil(inorder, postorder, inStart, inEnd, postIndex) {  if (inStart > inEnd) {  return null;  }  // Pick current node from Postorder traversal using  // postIndex and decrement postIndex  const node = new Node(postorder[postIndex[0]]);  postIndex[0]--;  // If this node has no children then return  if (inStart === inEnd) {  return node;  }  // Else find the index of this node in Inorder traversal  const inIndex = search(inorder, inStart, inEnd, node.data);  // Using index in Inorder traversal, construct left and  // right subtrees  node.right = buildUtil(inorder, postorder, inIndex + 1, inEnd, postIndex);  node.left = buildUtil(inorder, postorder, inStart, inIndex - 1, postIndex);  return node; } // This function mainly initializes index of root // and calls buildUtil() function buildTree(inorder, postorder) {  const n = inorder.length;  let postIndex = [n - 1];  return buildUtil(inorder, postorder, 0, n - 1, postIndex); } // Print the preorder of a binary tree function printPreorder(node) {  if (node === null) {  return;  }  console.log(node.data + " ");  printPreorder(node.left);  printPreorder(node.right); } const inorder = [4, 8, 2, 5, 1, 6, 3, 7]; const postorder = [8, 4, 5, 2, 6, 7, 3, 1]; const root = buildTree(inorder, postorder); printPreorder(root);

Output
1 2 4 8 5 3 6 7

[Expected Approach] Using hashing - O(n) Time and O(n) Space

The idea is to 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 postorder[]. The last node is lets say x, 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 x in inorder[] 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 right side in inorder[] and decrease index of postorder index .Make the created tree as right child of root. 
    • Recur for left side in inorder[] and decrease index of postorder index .Make the created tree as left child of root.
C++ 
// C++ program to construct a binary tree  // using inorder and postorder traversals #include <bits/stdc++.h> using namespace std; class Node { public:  int data;   Node* left;   Node* right;     Node(int x) {  data = x;  left = right = nullptr;  } }; // Function to recursively build the tree from // inorder and postorder traversals Node* buildUtil(vector<int>& inorder, vector<int>& postorder, int inStrt,   int inEnd, int& pIndex, unordered_map<int, int>& mp) {    // if start index exceeds end index, return NULL  if (inStrt > inEnd)  return NULL;  // Get the current node value from postorder   // traversal using pIndex and decrement pIndex  int curr = postorder[pIndex];  Node* node = new Node(curr);   pIndex--;  // If the current node has no children   // (inStrt == inEnd), return the node  if (inStrt == inEnd)  return node;  // Find the index of the current node's  // value in the inorder traversal  int iIndex = mp[curr];  // Recursively build the right and left subtrees  node->right = buildUtil(inorder, postorder, iIndex + 1, inEnd, pIndex, mp);   node->left = buildUtil(inorder, postorder, inStrt, iIndex - 1, pIndex, mp);   return node;  } // Main function to build the binary tree  // from inorder and postorder vectors Node* buildTree(vector<int>& inorder, vector<int>& postorder) {  int len = inorder.size();     // Create an unordered map to store the   // indexes of inorder elements for quick lookup  unordered_map<int, int> mp;  for (int i = 0; i < len; i++)  mp[inorder[i]] = i;  // Initialize postorder index as the last element  int postIndex = len - 1;    // Call the recursive utility function to build the tree  return buildUtil(inorder, postorder, 0, len - 1, postIndex, mp); } void print(Node* curr) {  if (curr == nullptr)  return;  cout<< curr->data << " ";  print(curr->left);  print(curr->right); } int main() {    vector<int> inorder = { 4, 8, 2, 5, 1, 6, 3, 7 };  vector<int> postorder = { 8, 4, 5, 2, 6, 7, 3, 1 };  Node* root = buildTree(inorder, postorder);  print(root);  return 0; }
Java 
// Java program to construct a binary tree  // using inorder and postorder traversals import java.util.*; class Node {  int data;  Node left, right;  Node(int x) {  data = x;  left = right = null;  } } class GfG {    // Function to recursively build the tree from  // inorder and postorder traversals  static Node buildUtil(List<Integer> inorder, List<Integer> postorder, int inStrt,   int inEnd, int[] pIndex, Map<Integer, Integer> mp) {    // if start index exceeds end index, return null  if (inStrt > inEnd)  return null;  // Get the current node value from postorder  // traversal using pIndex and decrement pIndex  int curr = postorder.get(pIndex[0]);  Node node = new Node(curr);  pIndex[0]--;  // If the current node has no children  // (inStrt == inEnd), return the node  if (inStrt == inEnd)  return node;  // Find the index of the current node's  // value in the inorder traversal  int iIndex = mp.get(curr);  // Recursively build the right and left subtrees  node.right = buildUtil(inorder, postorder, iIndex + 1, inEnd, pIndex, mp);  node.left = buildUtil(inorder, postorder, inStrt, iIndex - 1, pIndex, mp);  return node;  }  // Main function to build the binary tree  // from inorder and postorder vectors  static Node buildTree(List<Integer> inorder, List<Integer> postorder) {  int len = inorder.size();    // Create an unordered map to store the  // indexes of inorder elements for quick lookup  Map<Integer, Integer> mp = new HashMap<>();  for (int i = 0; i < len; i++)  mp.put(inorder.get(i), i);  // Initialize postorder index as the last element  int[] postIndex = new int[]{len - 1};  // Call the recursive utility function to build the tree  return buildUtil(inorder, postorder, 0, len - 1, postIndex, mp);  }  // Function to print preorder traversal of the tree  static void print(Node curr) {  if (curr == null)  return;  System.out.print(curr.data + " ");  print(curr.left);  print(curr.right);  }  public static void main(String[] args) {    List<Integer> inorder = Arrays.asList(4, 8, 2, 5, 1, 6, 3, 7);  List<Integer> postorder = Arrays.asList(8, 4, 5, 2, 6, 7, 3, 1);  Node root = buildTree(inorder, postorder);  print(root);  } }
Python 
# Python program to construct a binary tree  # using inorder and postorder traversals class Node: def __init__(self, x): self.data = x self.left = None self.right = None # Function to recursively build the tree from # inorder and postorder traversals def buildUtil(inorder, postorder, inStrt, inEnd, pIndex, mp): # if start index exceeds end index, return None if inStrt > inEnd: return None # Get the current node value from postorder # traversal using pIndex and decrement pIndex curr = postorder[pIndex[0]] node = Node(curr) pIndex[0] -= 1 # If the current node has no children # (inStrt == inEnd), return the node if inStrt == inEnd: return node # Find the index of the current node's # value in the inorder traversal iIndex = mp[curr] # Recursively build the right and left subtrees node.right = buildUtil(inorder, postorder, iIndex + 1, inEnd, pIndex, mp) node.left = buildUtil(inorder, postorder, inStrt, iIndex - 1, pIndex, mp) return node # Main function to build the binary tree # from inorder and postorder vectors def buildTree(inorder, postorder): # Create a dictionary to store the # indexes of inorder elements for quick lookup mp = {val: idx for idx, val in enumerate(inorder)} # Initialize postorder index as the last element pIndex = [len(postorder) - 1] # Call the recursive utility function to build the tree return buildUtil(inorder, postorder, 0, len(inorder) - 1, pIndex, mp) # Function to print preorder traversal of the tree def printTree(curr): if curr is None: return print(curr.data, end=" ") printTree(curr.left) printTree(curr.right) if __name__ == "__main__": inorder = [4, 8, 2, 5, 1, 6, 3, 7] postorder = [8, 4, 5, 2, 6, 7, 3, 1] root = buildTree(inorder, postorder) printTree(root)
C# 
// C# program to construct a binary tree  // using inorder and postorder traversals using System; using System.Collections.Generic; class Node {  public int data;  public Node left, right;  public Node(int x) {  data = x;  left = right = null;  } } class GfG {    // Function to recursively build the tree from  // inorder and postorder traversals  static Node BuildUtil(List<int> inorder, List<int> postorder, int inStrt,   int inEnd, ref int pIndex, Dictionary<int, int> mp) {    // if start index exceeds end index, return null  if (inStrt > inEnd)  return null;  // Get the current node value from postorder  // traversal using pIndex and decrement pIndex  int curr = postorder[pIndex];  Node node = new Node(curr);  pIndex--;  // If the current node has no children  // (inStrt == inEnd), return the node  if (inStrt == inEnd)  return node;  // Find the index of the current node's  // value in the inorder traversal  int iIndex = mp[curr];  // Recursively build the right and left subtrees  node.right = BuildUtil(inorder, postorder, iIndex + 1, inEnd, ref pIndex, mp);  node.left = BuildUtil(inorder, postorder, inStrt, iIndex - 1, ref pIndex, mp);  return node;  }  // Main function to build the binary tree  // from inorder and postorder vectors  static Node buildTree(List<int> inorder, List<int> postorder) {    // Create a dictionary to store the  // indexes of inorder elements for quick lookup  Dictionary<int, int> mp = new Dictionary<int, int>();  for (int i = 0; i < inorder.Count; i++)  mp[inorder[i]] = i;  // Initialize postorder index as the last element  int postIndex = postorder.Count - 1;  // Call the recursive utility function  // to build the tree  return BuildUtil(inorder, postorder, 0,  inorder.Count - 1, ref postIndex, mp);  }  // Function to print preorder traversal of the tree  static void Print(Node curr) {  if (curr == null)  return;  Console.Write(curr.data + " ");  Print(curr.left);  Print(curr.right);  }  static void Main(string[] args) {    List<int> inorder = new List<int>{ 4, 8, 2, 5, 1, 6, 3, 7 };  List<int> postorder = new List<int>{ 8, 4, 5, 2, 6, 7, 3, 1 };  Node root = buildTree(inorder, postorder);  Print(root);  } }
JavaScript 
// JavaScript program to construct a binary tree  // using inorder and postorder traversals class Node {  constructor(x) {  this.data = x;   this.left = null;   this.right = null;   } } // Function to recursively build the tree from // inorder and postorder traversals function buildUtil(inorder, postorder, inStrt, inEnd, pIndex, mp) {  // If start index exceeds end index, return null  if (inStrt > inEnd) {  return null;  }  // Get the current node value from postorder   // traversal using pIndex and decrement pIndex  const curr = postorder[pIndex[0]];  const node = new Node(curr);  pIndex[0]--;   // If the current node has no children   // (inStrt == inEnd), return the node  if (inStrt === inEnd) {  return node;  }  // Find the index of the current node's  // value in the inorder traversal  const iIndex = mp[curr];  // Recursively build the right and left subtrees  node.right = buildUtil(inorder, postorder, iIndex + 1, inEnd, pIndex, mp);  node.left = buildUtil(inorder, postorder, inStrt, iIndex - 1, pIndex, mp);  return node; } function buildTree(inorder, postorder) { const len = inorder.length;  const mp = {};  for (let i = 0; i < len; i++) {  mp[inorder[i]] = i;  }  // Initialize postorder index as the last element  const postIndex = [len - 1];  // Call the recursive utility function to build the tree  return buildUtil(inorder, postorder, 0, len - 1, postIndex, mp); } // Function to print the binary tree in preorder function print(curr) {  if (curr === null) {  return;  }  console.log(curr.data + " ");   print(curr.left);  print(curr.right); } // Inorder and postorder traversals  // of the binary tree const inorder = [4, 8, 2, 5, 1, 6, 3, 7]; const postorder = [8, 4, 5, 2, 6, 7, 3, 1]; const root = buildTree(inorder, postorder); print(root);

Output
1 2 4 8 5 3 6 7

Related articles:


K

kartik

Explore

Article Tags :
Lightbox