Tree From Pre-Order and Post-Order Walks

Medium

Two walks were recorded over a binary tree whose nodes hold the numbers 1 to n, each exactly once: - preorder_vals, the pre-order walk: the node first, then its left subtree, then its right subtree; - postorder_vals, the post-order walk: left subtree, then right subtree, and only then the node itself. Rebuild the tree and return its root. These two walks cannot tell whether an only child is a left or a right one, so use this convention: when a node has exactly one child, make it the **left** child. With that rule the answer is unique. Both lists are guaranteed to come from the same tree.

Example 1

preorder_vals=[1, 2, 4, 3, 5], postorder_vals=[4, 2, 5, 3, 1] → [1, 2, 3, 4, None, 5]

The root is 1. The next pre-order value, 2, roots the left subtree; in the post-order walk 2 comes right after 4, so the left subtree is {2, 4} and the right one is {3, 5}. Node 2 has the single child 4 and node 3 the single child 5; by the rule both become left children.

Example 2

preorder_vals=[1, 2, 3], postorder_vals=[3, 2, 1] → [1, 2, None, 3]

The walks cannot tell which side the children hang on, so each only child is a left child: a left chain 1 → 2 → 3.

Example 3

preorder_vals=[2, 1, 3], postorder_vals=[1, 3, 2] → [2, 1, 3]

Constraints

1 ≤ n = len(preorder_vals) ≤ 30
len(postorder_vals) = n
Each list is a permutation of 1 to n
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 Pre-Order and In-Order Walks Medium Tree From In-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=[1, 2, 4, 3, 5], postorder_vals=[4, 2, 5, 3, 1]

Expected

[1, 2, 3, 4, None, 5]

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