Reconstruct a binary tree from its in-order and post-order traversals (all values distinct) and return the root.
buildTreeInPost(inorder, postorder)
Input format: inorder | postorder (space-separated values). Output the tree in
level-order form (x for missing children).
inorder=9 3 15 20 7, postorder=9 15 7 20 3 // → 3 9 20 x x 15 7
inorder=1, postorder=1 // → 1
Reconstructing a tree from two traversals works because each encodes complementary information. In-order tells you which values fall left versus right of a subtree's root, but never which value is the root. Post-order tells you exactly which value is the root — its last element — but not where the left/right split falls. Together, each supplies what the other is missing.
Post-order visits left-subtree, right-subtree, node. So a subtree's own root is always the last thing recorded — everything before it belongs to its children. For the whole tree, the last value in the full post-order sequence is the overall root.
Find the root's value in the in-order sequence. Since in-order visits left, node, right, everything before that position belongs to the left subtree, everything after to the right. "I know the root" becomes "I know exactly which values form each subtree."
Work over a shrinking in-order window (lo/hi), with a pointer into post-order pointing at the next unconsumed value from the end. At each call: the current last unconsumed post-order value is this subtree's root; find its position in the in-order window for the split. Since post-order is left, then right, then node, the value just before the root belongs to the right subtree — so build the right subtree first, then the left, to consume post-order back-to-front correctly. lo exceeding hi means an empty subtree.
A value-to-index lookup over in-order turns finding the split into O(1) instead of a linear scan, so each of the n calls does constant extra work — O(n) time, O(n) space for the lookup table and the tree.
def build_tree_in_post(inorder, postorder):
index_of = {v: i for i, v in enumerate(inorder)}
post_idx = len(postorder) - 1
def build(lo, hi):
nonlocal post_idx
if lo > hi:
return None
val = postorder[post_idx]
post_idx -= 1
node = TreeNode(val)
mid = index_of[val]
node.right = build(mid + 1, hi)
node.left = build(lo, mid - 1)
return node
return build(0, len(inorder) - 1)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.