Preorder, inorder and postorder differ in when a node is processed relative to children. Choose the order from dependency of the computation.
Before you start
You should know arrays, loops and basic complexity notation. Start with a small input you can trace by hand. State what each variable means and which invariant is maintained, then use that invariant to explain correctness before discussing performance or writing a more compact solution.
The practical goal is to reason through this situation: Subtree size uses postorder because both child sizes are needed first. Read the walkthrough first, then try the interview exercise before opening its answer. The important part is explaining the decision and its consequences, rather than remembering a definition alone.
Step-by-step walkthrough
Step 1: Identify needed information
A parent’s height depends on both child heights.
Step 2: Choose postorder
Compute child results before combining at the parent.
Step 3: State the base convention
Empty height zero gives leaf height one; another convention changes reported values.
Worked scenario
Subtree size uses postorder because both child sizes are needed first.
A leaf receives child heights zero and zero, so its height is one. Its parent with another empty branch receives one and zero, returning two. This computation works for any binary tree; inorder sorted output requires a BST invariant and is a separate property.
Common mistake
Inorder gives sorted order only under the appropriate binary-search-tree invariant.
Verify the behavior
Test empty, leaf, balanced and skewed trees under the stated convention.
Interview exercise
Compute tree height.
Answer and reasoning
Return one plus the maximum child height after computing children, using a stated empty-tree convention.
Continue learning
Compare the scenario with the Data Structures and Algorithms interview questions and test your understanding with the Data Structures and Algorithms MCQs. For terminology and implementation details, consult the reference material.