Pattern visualizer

Construct Binary Tree from Preorder and Inorder Traversal

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. 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]..

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

time O(n)space O(n)step 1 / 15

Call stack

build(0, 4)

line 7

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

Where to practice Binary Trees

Practice Binary Trees problems All Binary Trees problems Back to roadmap