Trees · 115Medium
Construct Binary Tree from Preorder and Inorder Traversal
Given two arrays preorder and inorder representing the traversals of the same binary tree with unique values, reconstruct and return the tree.
Constraints
- 1 <= preorder.length <= 3000
- inorder.length == preorder.length
- All values are unique, and inorder is a genuine in-order traversal of the same tree.
- INPUT FORMAT
- `root` is a TreeNode object, not an array. The arrays in EXAMPLES are the level-order
- serialization the platforms print — breadth-first, with `null` for a missing child. The
- test runner builds a real tree from that array before calling your function.
Examples
buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]) -> [3, 9, 20, null, null, 15, 7] buildTree([-1], [-1]) -> [-1] buildTree([1, 2], [2, 1]) -> [1, 2] // two nodes, leaning left buildTree([1, 2], [1, 2]) -> [1, null, 2] // leaning right buildTree([1, 2, 3, 4], [4, 3, 2, 1]) -> [1, 2, null, 3, null, 4] // skewed buildTree([1, 2, 4, 5, 3, 6, 7], [4, 2, 5, 1, 6, 3, 7]) -> [1, 2, 3, 4, 5, 6, 7] // balanced
Edge cases
- A single node.
Show the target complexity (spoiler)
- Naive
- O(n^2) time — a fresh linear scan of inorder to locate each root.
- Target
- O(n) time — a value-to-index map over inorder for O(1) root lookup, recursing with index ranges rather than array slices.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/07-trees/115-construct-binary-tree-from-preorder-and-inorder-traversal.js ./practice c 115