Height of Binary Tree in DSA C - Execution Trace

Concept Flow - Height of Binary Tree

Start at root node

↓

Is node NULL?

Yes→Return 0

No↓

Compute height of left subtree

↓

Compute height of right subtree

↓

Height = max(left, right) + 1

↓

Return height

We start at the root and recursively find the height of left and right subtrees. The height of the node is the larger height of its children plus one.

Execution Sample

DSA C

int height(struct Node* root) {
  if (root == NULL) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

This code calculates the height of a binary tree by recursively finding the height of left and right subtrees and returning the maximum plus one.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Computed	Tree State
1	Start at root	1	-	-	-	1 / \ 2 3
2	Go left	2	-	-	-	1 / \ 2 3
3	Go left	4	-	-	-	1 / \ 2 3 / 4
4	Left child NULL	NULL	0	-	-	1 / \ 2 3 / 4
5	Right child NULL	NULL	-	0	-	1 / \ 2 3 / 4
6	Compute height at node 4	4	0	0	1	1 / \ 2 3 / 4(1)
7	Go right of 2	5	-	-	-	1 / \ 2 3 / \ 4 5
8	Left child NULL	NULL	0	-	-	1 / \ 2 3 / \ 4 5
9	Right child NULL	NULL	-	0	-	1 / \ 2 3 / \ 4 5
10	Compute height at node 5	5	0	0	1	1 / \ 2 3 / \ 4(1) 5(1)
11	Compute height at node 2	2	1	1	2	1 / \ 2(2) 3 / \ 4(1) 5(1)
12	Go right of root	3	-	-	-	1 / \ 2(2) 3 / \ 4(1) 5(1)
13	Left child NULL	NULL	0	-	-	1 / \ 2(2) 3 / \ 4(1) 5(1)
14	Right child NULL	NULL	-	0	-	1 / \ 2(2) 3 / \ 4(1) 5(1)
15	Compute height at node 3	3	0	0	1	1 / \ 2(2) 3(1) / \ 4(1) 5(1)
16	Compute height at root	1	2	1	3	1(3) / \ 2(2) 3(1) / \ 4(1) 5(1)
17	Return final height	-	-	-	3	Tree height is 3

💡 Recursion ends when node is NULL, returning 0 height for empty subtree.

Variable Tracker

Variable	Start	After Step 6	After Step 10	After Step 11	After Step 15	After Step 16	Final
root	Node 1	Node 2	Node 5	Node 2	Node 3	Node 1	NULL (end)
leftHeight	-	0 (node 4)	0 (node 5)	1 (node 2)	0 (node 3)	2 (node 1)	-
rightHeight	-	0 (node 4)	0 (node 5)	1 (node 2)	0 (node 3)	1 (node 1)	-
height	-	1 (node 4)	1 (node 5)	2 (node 2)	1 (node 3)	3 (node 1)	3

Key Moments - 3 Insights

Why do we return 0 when the node is NULL?

Returning 0 for NULL nodes means empty subtrees have height 0, which is the base case stopping recursion (see Step 4 and 5).

Why do we add 1 after taking max of left and right heights?

We add 1 to count the current node itself, so height includes the node plus the tallest subtree (see Step 6, 11, 15, 16).

How does recursion ensure all nodes are visited?

The function calls itself on left and right children until NULL, so every node is processed bottom-up (see Steps 2, 3, 7, 12).

Visual Quiz - 3 Questions

Look at the execution table, what is the height computed at node 2 (Step 11)?

A 3

B 1

C 2

D 0

💡 Hint

Check the 'Height Computed' column at Step 11 in the execution_table.

At which step does the recursion return height 1 for node 5?

A Step 10

B Step 6

C Step 15

D Step 16

💡 Hint

Look for node 5 and height 1 in the 'Height Computed' column in execution_table.

If the right subtree of root was NULL, what would be the final height?

A 1

B 3

C 2

D 0

💡 Hint

Refer to variable_tracker for rightHeight at root and how height is max(left, right) + 1.

Concept Snapshot

Height of Binary Tree:
- Base case: NULL node height = 0
- Recursively find left and right subtree heights
- Height = max(leftHeight, rightHeight) + 1
- Counts nodes along longest path from root to leaf
- Uses post-order traversal (left, right, node)

Full Transcript

To find the height of a binary tree, start at the root node. If the node is NULL, return 0 as the height. Otherwise, recursively find the height of the left subtree and the right subtree. The height of the current node is the maximum of these two heights plus one to include the current node. This process continues until all nodes are visited. The final height is the number of nodes along the longest path from the root to a leaf. The recursion stops when it reaches NULL nodes, which represent empty subtrees with height zero.

Practice

1. What is the height of a binary tree with only one node (the root)?

easy

A. 0

B. 1

C. 2

D. Undefined

Solution

1. Step 1: Understand height definition

   The height of a binary tree is the number of edges on the longest path from the root to a leaf.

2. Step 2: Apply to single node tree

   With only one node (root), the longest path has length 0 edges.

3. Final Answer:

   0 -> Option A

4. Quick Check:

   Height of single node tree = 0 [OK]

Hint: Height counts edges on longest root-to-leaf path [OK]

Common Mistakes:

• Thinking height is 1 for single node
• Confusing height with number of nodes
• Assuming height is undefined for single node

2. Which of the following is the correct C function signature to calculate the height of a binary tree node?

easy

A. void height(struct Node root);

B. int height(Node root);

C. int height(struct Node* root);

D. int height(struct Node root);

Solution

1. Step 1: Check parameter type for tree node

   In C, a tree node is usually passed as a pointer to struct Node.

2. Step 2: Check return type and parameter correctness

   The function returns an int (height) and takes a pointer to struct Node.

3. Final Answer:

   int height(struct Node* root); -> Option C

4. Quick Check:

   Correct signature uses pointer to struct Node [OK]

Hint: Use pointer to struct Node for tree parameters [OK]

Common Mistakes:

• Passing struct Node by value instead of pointer
• Using void return type instead of int
• Missing struct keyword in parameter

3. What is the output of the following code snippet calculating the height of this binary tree?

struct Node {
  int data;
  struct Node* left;
  struct Node* right;
};

int height(struct Node* root) {
  if (root == NULL) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

// Tree:
//     10
//    /  \
//   5    15
//        /
//       12

int main() {
  struct Node n12 = {12, NULL, NULL};
  struct Node n15 = {15, &n12, NULL};
  struct Node n5 = {5, NULL, NULL};
  struct Node n10 = {10, &n5, &n15};
  printf("%d", height(&n10));
  return 0;
}

medium

A. 1

B. 2

C. 4

D. 3

Solution

1. Step 1: Trace left subtree height

   Left subtree of root (10) has node 5 only, height = 1.

2. Step 2: Trace right subtree height

   Right subtree has nodes 15 and 12. Height is 2 (15 -> 12).

3. Step 3: Calculate total height

   Height = max(1, 2) + 1 (for root) = 3.

4. Final Answer:

   3 -> Option D

5. Quick Check:

   Height = 3 [OK]

Hint: Height = max(left, right) + 1 recursively [OK]

Common Mistakes:

• Counting edges instead of nodes
• Ignoring one subtree height
• Off-by-one error in return statement

4. Identify the error in this height function and select the correct fix:

int height(struct Node* root) {
  if (root == NULL) return -1;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

medium

A. Change base case return from -1 to 1

B. Change base case return from -1 to 0

C. Remove +1 from return statement

D. Change recursive calls to root->right and root->left swapped

Solution

1. Step 1: Understand base case meaning

   Base case returns height for empty tree. Returning -1 means height counts edges, not nodes.

2. Step 2: Fix base case for node count height

   To count nodes, base case should return 0 for NULL.

3. Final Answer:

   Change base case return from -1 to 0 -> Option B

4. Quick Check:

   Base case 0 for NULL node height [OK]

Hint: Base case for NULL should return 0 for node height [OK]

Common Mistakes:

• Returning -1 causes off-by-one height
• Removing +1 leads to wrong height
• Swapping left and right recursive calls unnecessary

5. Given a binary tree where each node has either 0 or 2 children, what is the height of a full binary tree with 7 nodes? Select the correct height.

hard

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Understand full binary tree properties

   A full binary tree with all nodes having 0 or 2 children has nodes count = 2^h - 1, where h is height.

2. Step 2: Calculate height from nodes count

   Given nodes = 7, solve 2^h - 1 = 7 -> 2^h = 8 -> h = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Full binary tree height for 7 nodes = 3 [OK]

Hint: Full tree nodes = 2^height - 1 formula [OK]

Common Mistakes:

• Confusing height with number of edges
• Using incomplete binary tree formula
• Miscounting nodes or height