Tree From In-Order and Post-Order Walks

Medium

Two walks were recorded over a binary tree whose node values are all distinct: - inorder_vals, the in-order walk: left subtree, then the node, then the 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. Both lists are guaranteed to come from the same tree.

Example 1

inorder_vals=[4, 8, 2, 6, 5], postorder_vals=[4, 2, 8, 5, 6] → [6, 8, 5, 4, 2]

The last value of the post-order walk, 6, is the root. In the in-order walk, [4, 8, 2] lies left of 6 (the left subtree) and [5] lies right. In the left subtree the root is 8 (last of 4, 2, 8), with children 4 and 2.

Example 2

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

The root is 1 and nothing is left of it in the in-order walk, so everything goes right: a chain 1 → 2 → 3.

Example 3

inorder_vals=[-7], postorder_vals=[-7] → [-7]

Constraints

1 ≤ len(inorder_vals) ≤ 3000
len(postorder_vals) = len(inorder_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 Pre-Order and In-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

inorder_vals=[4, 8, 2, 6, 5], postorder_vals=[4, 2, 8, 5, 6]

Expected

[6, 8, 5, 4, 2]

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