DSA
Construct Binary Tree from Inorder and Postorder Traversal
Binary Trees problem — solution with code and analysis.
Practice here
Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.
Approach#
- Intuition: In a postorder traversal the very last element is the root of the current subtree. Once the root is identified, its position in the inorder array separates the left and right subtrees — elements to the left of the root in inorder form the left subtree and elements to the right form the right subtree.
- Mechanics: A hash map precomputes each value's index in inorder for O(1) lookups. A shared postIdx counter starts at the last element of postorder and decrements after each node is created. Crucially, the right subtree must be built before the left subtree because postorder visits left → right → root, so reading the array in reverse gives root → right → left.
- Trade-off: The hash map trades O(n) extra space for O(1) root-lookup at each recursive level, reducing total time from O(n²) (linear scan) to O(n) — the same strategy as the inorder+preorder variant, with the only structural difference being right-before-left recursion order.
cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTreeUtil(int inStart, int inEnd, vector<int>& postorder, int &postIdx, unordered_map<int,int> &inMap){
if(postIdx<0 || inStart>inEnd)
return NULL;
TreeNode* root = new TreeNode(postorder[postIdx--]);
int inIdx = inMap[root->val];
root->right = buildTreeUtil(inIdx+1, inEnd, postorder, postIdx, inMap);
root->left = buildTreeUtil(inStart, inIdx-1, postorder, postIdx, inMap);
return root;
}
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
int postIdx = postorder.size()-1;
unordered_map<int,int> inMap;
for(int i=0;i<inorder.size();i++)
inMap[inorder[i]]=i;
return buildTreeUtil(0, inorder.size()-1, postorder, postIdx, inMap);
}
};