DSA Tracker

Visualize

Construct Binary Tree from Preorder and Inorder Traversal

Preorder picks the root, inorder splits it into left and right

time O(n)space O(n)

Preorder always visits a subtree's root before either of its children, so the next unused preorder element is always the current subtree's root. Inorder always visits a subtree's left children, then its root, then its right children, so once you know the root's value, its position in inorder splits everything left of it into the left subtree and everything right of it into the right subtree. A hash map from value to inorder index makes that split O(1) instead of a scan.

Details

Animated on: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] — rebuild the binary tree these two traversals came from. Expected: [3,9,20,null,null,15,7].

Problem:Construct Binary Tree from Preorder and Inorder TraversalMedium

Preorder picks the root, inorder splits it into left and right

step 1 / 15

3

Call stack

build(0, 4)

preorder[0] = 3 is the next unused preorder element, so it becomes the root of inorder[0..4]. preIdx -> 1.

Pseudocode
1FUNCTION buildTree(preorder, inorder):
2  BUILD_INDEX_MAP(inorder)
3  preIdx <- 0
4  RETURN build(0, LENGTH(inorder) - 1)
5FUNCTION build(inStart, inEnd):
6  IF inStart > inEnd: RETURN null
7  val <- preorder[preIdx]; preIdx <- preIdx + 1
8  node <- NEW NODE(val)
9  mid <- indexMap[val]
10  node.left <- build(inStart, mid - 1)
11  node.right <- build(mid + 1, inEnd)
12  RETURN node

← / → step · space play · Home restart

Every step in words

Show all 15 steps
  1. preorder[0] = 3 is the next unused preorder element, so it becomes the root of inorder[0..4]. preIdx -> 1.
  2. Look up 3 in inorder: index 1. Everything left of it, inorder[0..0], is 3's left subtree; everything right, inorder[2..4], is its right subtree. Recurse left first.
  3. preorder[1] = 9 is the next unused preorder element, so it becomes the root of inorder[0..0]. preIdx -> 2.
  4. 9's range was a single element, so both child calls got an empty range (inStart > inEnd) and hit the base case immediately — 9 is a leaf. Its build call returns to the parent.
  5. 3's left subtree is done. Now recurse into its right subtree, inorder[2..4].
  6. preorder[2] = 20 is the next unused preorder element, so it becomes the root of inorder[2..4]. preIdx -> 3.
  7. Look up 20 in inorder: index 3. Everything left of it, inorder[2..2], is 20's left subtree; everything right, inorder[4..4], is its right subtree. Recurse left first.
  8. preorder[3] = 15 is the next unused preorder element, so it becomes the root of inorder[2..2]. preIdx -> 4.
  9. 15's range was a single element, so both child calls got an empty range (inStart > inEnd) and hit the base case immediately — 15 is a leaf. Its build call returns to the parent.
  10. 20's left subtree is done. Now recurse into its right subtree, inorder[4..4].
  11. preorder[4] = 7 is the next unused preorder element, so it becomes the root of inorder[4..4]. preIdx -> 5.
  12. 7's range was a single element, so both child calls got an empty range (inStart > inEnd) and hit the base case immediately — 7 is a leaf. Its build call returns to the parent.
  13. Both children of 20 are now attached (left = 15, right = 7), so build(2, 4) returns node 20.
  14. Both children of 3 are now attached (left = 9, right = 20), so build(0, 4) returns node 3.
  15. Done: level order is [3, 9, 20, null, null, 15, 7]. Every preorder element was used exactly once to create a node, so the whole build costs O(n) with the hash map (O(n^2) if the root's index is found by scanning instead).

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Construct Binary Tree from Preorder and Inorder Traversal in the editorAll Binary Trees problemsBack to roadmap