Reference: LeetCode 105, LeetCode 106 EPI 9.11
Difficulty: Medium

## Problem

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:

Example:

Return the following binary tree:

## Analysis

Methods:

1. Recursion
• Find Root: The node of preorder sequence from left to right is always the root of the current subtree.
• Split Subtree Nodes: According to the root, we can split nodes in the inorder array into two parts belonging to left and right subtrees.

Time: $O(N\log{N})$ in the best case, and $O(N^2)$ in the worst case, since at each level it takes $O(N)$ to find the root index.
Space: $O(h)$

1. Recursion (HashMap)
• Use a HashMap to map the values to indices.

Time: $O(N)$
Space: $O(N)$

Here is the version of Postorder + Inorder:

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.