Trees & triesLeetCode 105

Lesson 29 of 76

Construct Binary Tree from Preorder and Inorder Traversal

Rebuild a binary tree from its preorder and inorder traversals.

Watch on YouTube

Lesson notes

Try it before you watch

Restate the problem in your own words, list the edge cases, and sketch a solution with its running time. Then play the video and compare.

Reveal the key idea

The next preorder value is the root; its position in the inorder list splits the left and right subtrees. A dictionary of inorder positions makes each lookup O(1).

Pattern: Trees & tries. Most tree problems are a recursive question asked of the left subtree, the right subtree, and the root.

Complexity

Cost of the standard optimal approach for Construct Binary Tree from Preorder and Inorder Traversal
Measure Bound
Time O(n)
Extra space O(n)

Walkthroughs often start from a simpler approach first; aim to reach these bounds. New to Big-O? Read understanding algorithmic complexity.