Construct Binary Tree from Preorder and Inorder Traversal
The key idea
The first element of
preorder is always the current subtree's root. Finding that root inside inorder splits the remaining values into the left subtree (left of it) and the right subtree (right of it). A hash map from value to its inorder index makes each split O(1).Problem
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.
The tree contains only unique values, and every value in one array appears in the other. Your job is to recover the exact shape of the original tree from these two orderings.
Constraints
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorderandinorderconsist of unique values.- Each value of
inorderalso appears inpreorder. preorderis guaranteed to be the preorder traversal of the tree.inorderis guaranteed to be the inorder traversal of the tree.
Examples
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY
- Count Good Nodes in Binary TreeMEDIUM