Description
Rebuild a tree from valid preorder and inorder traversals with unique values.
Solution
import sys
sys.setrecursionlimit(100_000)
def build_tree(preorder, inorder):
positions = {value:i for i, value in enumerate(inorder)}
roots = iter(preorder)
def build(left, right):
if left > right:
return None
value = next(roots)
split = positions[value]
node = TreeNode(value)
node.left = build(left, split-1)
node.right = build(split+1, right)
return node
return build(0, len(inorder)-1)Examples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[2,1,3],[1,2,3]]- Output
[2,1,3]
Root 2 separates left value 1 and right value 3.
Example 2
- Input
[[7],[7]]- Output
[7]
Both traversals identify one leaf.
Example 3
- Input
[[1,2],[2,1]]- Output
[1,2]
Inorder places 2 to the left of root 1.
Approach
Consume preorder roots in order. An inorder index map splits each subtree without copying array slices.
Time & space
O(n) expected time; O(n) space including map and recursion, excluding output. Here n is the node count, and h is the tree height.