progress

~/problems / Trees / Binary trees

Construct Binary Tree from Preorder and Inorder Traversal

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~30 min

A binary tree with distinct values was saved as two lists, and the tree itself was lost:

  • preorder lists every node before its left subtree, and the left subtree before the right subtree.
  • inorder lists every node's left subtree, then the node, then its right subtree.

TreeNode(val, left=None, right=None) is in the starter. Keep it.

Write rebuild_tree(preorder, inorder) -> TreeNode: rebuild the tree and return its root. The two listings always describe exactly one tree. Empty lists mean an empty tree (None).

rebuild_tree([7, 3, 1, 5, 9, 8], [1, 3, 5, 7, 8, 9])
#          7
#         / \
#        3   9
#       / \  /
#      1  5 8
Preorder 7, 3, 1, 5, 9, 8 and inorder 1, 3, 5, 7, 8, 9: the first preorder value 7 splits the inorder list into a left subtree 1, 3, 5 and a right subtree 8, 9, giving the tree below them
rebuild_tree([], [])     # None
  • Up to 20,000 nodes; values are distinct integers between -10^9 and 10^9.
  • A tree can be as deep as it has nodes. If you recurse, raise the limit first (sys.setrecursionlimit(50_000)), or build with an explicit stack.
  • ⭐ Bonus: a speed test on a 12,000-node chain earns a star in O(n). Scanning inorder for every subtree's root, or slicing the lists at every step, is O(n²) there.
Show hint

The first value of preorder is the root, and its position in inorder tells you how many values belong to the left subtree. Look positions up in a dictionary built once, and pass index ranges instead of slices.

Topic: Binary trees. Recursive return values (height, best path), BFS by level, BST invariants.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc