Construct Binary Tree from Inorder and Postorder Traversal Solution
Construct Binary Tree from Inorder and Postorder Traversal solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Construct Binary Tree from Inorder and Postorder Traversal is a medium coding problem on arrays, hash table and trees, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Trees, Divide and Conquer
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two integer arrays: inorder, the inorder traversal of a binary tree (left subtree, node, right subtree), and postorder, the postorder traversal of the same tree (left subtree, right subtree, node). All values are distinct.
Rebuild the tree and return its root.
Example 1
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]
Explanation: 3 comes last in postorder, so it is the root; in the inorder list 9 is to its left and 15, 20, 7 to its right. Repeating the split on each side gives the tree.
Example 2
Input: inorder = [-1], postorder = [-1]
Output: [-1]
Explanation: A single node.
Example 3
Input: inorder = [1,2,3], postorder = [3,2,1]
Output: [1,null,2,null,3]
Explanation: Every value sits right of its parent in the inorder list, so the tree is a chain of right children.
Constraints
1 <= inorder.length <= 3000postorder.length == inorder.length-3000 <= inorder[i], postorder[i] <= 3000all values are distinctevery value of postorder appears in inorderthe two arrays describe the same tree
Hints for Construct Binary Tree from Inorder and Postorder Traversal
Hint 1
The last value of a postorder traversal is always the root.
Hint 2
Find the root in the inorder list: everything to its left is the left subtree, everything to its right the right subtree.
Hint 3
Walk postorder from the back with one shared pointer. Read backwards it lists node, right subtree, left subtree — so build the right subtree before the left. Look positions up in a hash map.
How to solve Construct Binary Tree from Inorder and Postorder Traversal
Postorder read from the end names each subtree's root first, then its right subtree, then its left; inorder says which values lie on each side of a root. Consuming postorder backwards while splitting inorder ranges rebuilds the tree.
Approach
- Map every value to its index in
inorder. - Keep a pointer
posintopostorder, starting at its last index. - To build the subtree whose values occupy
inorder[lo..hi]: iflo > hireturn null; otherwise takepostorder[pos]as the root and moveposone step left. - Let
midbe the root's index ininorder; build the right subtree from[mid + 1, hi]first, then the left subtree from[lo, mid - 1]. - Return the root built for the whole range.
Why it works
Postorder is left subtree, right subtree, node; reversed it is node, right subtree, left subtree — the mirror of preorder. Building the right subtree completely before the left therefore makes the backwards pointer meet exactly the roots the recursion needs, and the inorder position of each root splits its range correctly because values are distinct.
Complexity
- Time —
O(n) - Space —
O(n) for the map, O(h) for the recursion
Pitfalls
- Building the left subtree first, as in the preorder version, pairs the wrong roots with the ranges.
- Searching for the root in
inordereach time makes it O(n^2) on a chain.
Reference solution
Python
from typing import List, Optional
def buildTree(inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
index = {v: i for i, v in enumerate(inorder)}
pos = len(postorder) - 1
def build(lo, hi):
nonlocal pos
if lo > hi:
return None
v = postorder[pos]
pos -= 1
node = TreeNode(v)
mid = index[v]
node.right = build(mid + 1, hi)
node.left = build(lo, mid - 1)
return node
return build(0, len(inorder) - 1)Java
public static TreeNode buildTree(int[] inorder, int[] postorder) {
Map<Integer, Integer> index = new HashMap<>();
for (int i = 0; i < inorder.length; i++) index.put(inorder[i], i);
int[] pos = {postorder.length - 1};
return build(postorder, index, pos, 0, inorder.length - 1);
}
static TreeNode build(int[] postorder, Map<Integer, Integer> index, int[] pos, int lo, int hi) {
if (lo > hi) return null;
int v = postorder[pos[0]--];
TreeNode node = new TreeNode(v);
int mid = index.get(v);
node.right = build(postorder, index, pos, mid + 1, hi);
node.left = build(postorder, index, pos, lo, mid - 1);
return node;
}C++
TreeNode* buildRange(vector<int>& postorder, unordered_map<int, int>& index, int& pos, int lo, int hi);
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
unordered_map<int, int> index;
for (int i = 0; i < (int) inorder.size(); i++) index[inorder[i]] = i;
int pos = (int) postorder.size() - 1;
return buildRange(postorder, index, pos, 0, (int) inorder.size() - 1);
}
TreeNode* buildRange(vector<int>& postorder, unordered_map<int, int>& index, int& pos, int lo, int hi) {
if (lo > hi) return nullptr;
int v = postorder[pos--];
TreeNode* node = new TreeNode(v);
int mid = index[v];
node->right = buildRange(postorder, index, pos, mid + 1, hi);
node->left = buildRange(postorder, index, pos, lo, mid - 1);
return node;
}JavaScript
var buildTree = function(inorder, postorder) {
var index = new Map(), pos = postorder.length - 1;
for (var i = 0; i < inorder.length; i++) index.set(inorder[i], i);
function build(lo, hi) {
if (lo > hi) return null;
var v = postorder[pos--];
var node = new TreeNode(v);
var mid = index.get(v);
node.right = build(mid + 1, hi);
node.left = build(lo, mid - 1);
return node;
}
return build(0, inorder.length - 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets