Given the output of a postorder traversal is [4, 5, 2, 6, 7, 3, 1], which of the following binary trees could produce this output?

hard🔄 Reverse Engineer Q9 of Q15

Tree: Depth-First Search - Binary Tree Postorder Traversal

ARoot 1 with left child 2 (children 4,5) and right child 3 (children 6,7)

BRoot 1 with left child 3 (children 6,7) and right child 2 (children 4,5)

CRoot 1 with left child 2 (children 5,4) and right child 3 (children 7,6)

DRoot 1 with left child 3 (children 7,6) and right child 2 (children 5,4)

Step-by-Step Solution

Solution:

Step 1: Analyze postorder output
Postorder is left subtree, right subtree, root. Output ends with 1, root.
Step 2: Match left and right subtree outputs
Left subtree output is [4,5,2], right subtree is [6,7,3].
Step 3: Identify tree structure
Root 1 with left child 2 (children 4,5) and right child 3 (children 6,7) matches the output.
Final Answer:
Option A -> Option A
Quick Check:
Output matches postorder of Root 1 with left child 2 (children 4,5) and right child 3 (children 6,7) tree [OK]

Quick Trick: Postorder ends with root, sublists are subtrees [OK]

Common Mistakes:

MISTAKES

Trap Explanation:

PITFALL

Candidates often confuse left and right subtree outputs or child order in postorder.

Interviewer Note:

CONTEXT

Master "Binary Tree Postorder Traversal" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

More Tree: Depth-First Search Quizzes