Construct Binary Tree from Preorder and Inorder

LeetCode 105 • Medium • Trees

Given two integer arrays preorder and inorder representing traversals of the same binary tree, reconstruct the tree. First value in preorder is always the root; split inorder into left and right subtrees at that value.

TimeO(n)hash index

SpaceO(n)map + stack

Step0/0

preorder: 3 9 20 15 7 inorder: 9 3 15 20 7

Ready

Preorder is root → left → right. Inorder is left → root → right. The root splits inorder into left and right segments.

Speed:

✎ Whiteboard

Size:3

⌨ Type It

Implement buildTree(preorder, inorder) returning TreeNode.

═══ RECURSIVE ═══

root = preorder[0]; find root in inorder → idx

left = build(pre[1:1+idx], in[:idx])

right = build(pre[1+idx:], in[idx+1:])

Verify:

⌨ Type It — Iterative

Verify: