[Solved] Consider the following iterative postorder traversal code to check if a binary tree is balanced. Given the tree:... What is the value of heights[root] after the traversal completes? | Tree: Depth-First Search

Tree: Depth-First Search - Balanced Binary Tree

Consider the following iterative postorder traversal code to check if a binary tree is balanced. Given the tree: root=1, left=2, right=3, and node 2 has left child 4. What is the value of heights[root] after the traversal completes?

A2

B1

C3

D4

Step-by-Step Solution

Solution:

Step 1: Trace heights for leaf nodes
Node 4 is a leaf, so heights[4] = 1.
Step 2: Compute heights bottom-up
Node 2 has left child 4 (height 1) and no right child (height 0), so heights[2] = 1 + max(1,0) = 2. Node 3 is leaf, heights[3] = 1. Root 1 has children heights 2 and 1, so heights[1] = 1 + max(2,1) = 3.
Final Answer:
Option C -> Option C
Quick Check:
Height of root is max height of subtrees plus one [OK]

Quick Trick: Height of root equals max subtree height plus one [OK]

Common Mistakes:

MISTAKES

Forgetting to add 1 for current node height
Mixing up left and right subtree heights
Returning height instead of boolean balance

Trap Explanation:

PITFALL

Option B looks plausible if candidate forgets to add 1 at root; option D is too large for given tree.

Interviewer Note:

CONTEXT

Tests candidate's ability to mentally execute iterative postorder traversal and height calculation.

Master "Balanced Binary Tree" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Tree: Depth-First Search Quizzes

What is the value of heights[root] after the traversal completes?

Step 1: Trace heights for leaf nodes

Step 2: Compute heights bottom-up

Final Answer:

Quick Check:

Want More Practice?