Tree From Pre-Order and In-Order Walks

Medium

Two walks were recorded over a binary tree whose node values are all distinct: - preorder_vals, the pre-order walk: the node first, then its left subtree, then its right subtree; - inorder_vals, the in-order walk: left subtree, then the node, then the right subtree. Rebuild the tree and return its root. Both lists are guaranteed to come from the same tree.

Example 1

preorder_vals=[5, 3, 1, 4, 8], inorder_vals=[1, 3, 4, 5, 8] → [5, 3, 8, 1, 4]

The first value of the pre-order walk, 5, is the root. In the in-order walk, [1, 3, 4] lies left of 5 and [8] lies right. The left subtree starts with 3 (next in pre-order), with children 1 and 4.

Example 2

preorder_vals=[10, 20, 30], inorder_vals=[30, 20, 10] → [10, 20, None, 30]

Each next node sits to the left of the previous one in the in-order walk, so the tree is a left chain 10 → 20 → 30.

Example 3

preorder_vals=[0], inorder_vals=[0] → [0]

Constraints

1 ≤ len(preorder_vals) ≤ 3000
len(inorder_vals) = len(preorder_vals)
-3000 ≤ values ≤ 3000
All values are distinct
Both lists are walks of the same tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Array Hash Table Divide and Conquer Binary Tree

Similar problems

Tree From In-Order and Post-Order Walks Medium Tree From Pre-Order and Post-Order Walks Medium Peak-Split Tree Medium Path Totals in a Coded Tree Medium Tree From Parent Links Medium

Input

preorder_vals=[5, 3, 1, 4, 8], inorder_vals=[1, 3, 4, 5, 8]

Expected

[5, 3, 8, 1, 4]

Run checks the first 3 tests in your browser. Submit checks all 64 tests on the server, hidden ones included.