PPractick

The problem

A compiler dumps expression trees as their inorder and postorder sequences (all node IDs distinct), and a debugger must rebuild the tree. Postorder lists the root last, so read postorder from the end. Each value taken is the root of the current inorder range, and its position in inorder splits the range into left and right parts. Reading backwards, postorder gives root, then the right subtree, then the left, so the right subtree must be built first.

Example: inorder [9, 3, 15, 20, 7], postorder [9, 15, 7, 20, 3] → [3, 9, 20, null, null, 15, 7].

Function signature

TreeNode* buildTree(const vector<int>& inorder, const vector<int>& postorder);

Test cases

Input (inorder, postorder)	Output (level order)	Explanation
([9, 3, 15, 20, 7], [9, 15, 7, 20, 3])	[3, 9, 20, null, null, 15, 7]
([4, 2, 5, 1, 6, 3, 7], [4, 5, 2, 6, 7, 3, 1])	[1, 2, 3, 4, 5, 6, 7]
([2, 1], [2, 1])	[1, 2]	2 is a left child
([1, 2], [2, 1])	[1, null, 2]	2 is a right child
([-1], [-1])	[-1]

(Confirm: values are distinct and both arrays describe the same tree.)

How interviewers phrase it

• "Given inorder and postorder traversals of a binary tree, construct and return the tree" (LeetCode 106).

Clarifying questions to ask

1. Are values unique? (Yes.)
2. Are the arrays consistent? (Yes.)
3. How large is n? (Up to 3000, so recursion depth could be 3000 for a skewed tree.)

Follow-ups to expect

1. "Why walk postorder backwards?"
2. "Why build the right subtree first?"
3. "How is this different from preorder + inorder?"
4. "Iterative version?"
5. "Complexity?"

Related questions

• Construct a BT from Preorder and Inorder Hard
• LCA in BT Hard
• Preorder Traversal Easy
• Inorder Traversal of Binary Tree Easy
• Postorder Traversal Easy
• Maximum Depth in BT Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in