DSA
Construct Binary Tree from Preorder and Inorder Traversal
Binary Trees problem — solution with code and analysis.
Pratice here
Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.
Approach#
- Intuition: In a preorder traversal the very first element is always the root of the current subtree. Knowing the root lets you locate it in the inorder array — everything to its left in inorder belongs to the left subtree, and everything to its right belongs to the right subtree. Repeating this recursively rebuilds the entire tree.
- Mechanics: A hash map indexes each value's position in the inorder array for O(1) lookup. A shared preIdx counter advances through preorder one element at a time, always pointing to the root of the current subproblem. After creating a node, the algorithm recurses first into the left range (inStart … inIdx-1) and then into the right range (inIdx+1 … inEnd), which naturally matches the left-before-right order of preorder.
- Trade-off: The hash map raises space usage from O(n) stack to O(n) total, but eliminates the O(n) linear scan to find the root in inorder at each level — bringing the overall time from O(n²) to O(n).
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>& preorder, int &preIdx, unordered_map<int,int> &inMap){
if(preIdx>= preorder.size() || inStart>inEnd)
return NULL;
TreeNode* root = new TreeNode(preorder[preIdx++]);
int inIdx = inMap[root->val];
root->left = buildTreeUtil(inStart, inIdx-1, preorder, preIdx, inMap);
root->right = buildTreeUtil(inIdx+1, inEnd, preorder, preIdx, inMap);
return root;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int preIdx = 0;
unordered_map<int,int> inMap;
for(int i=0;i<inorder.size();i++)
inMap[inorder[i]]=i;
return buildTreeUtil(0, inorder.size()-1, preorder, preIdx, inMap);
}
};