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↓

Find height of left subtree

↓

Find height of right subtree

↓

Compare left and right heights

↓

Return max(left, right) + 1

↓

End

Start at the root, recursively find the height of left and right subtrees, then return the larger height plus one.

Execution Sample

DSA C++

int height(Node* root) {
  if (root == nullptr) return 0;
  int leftHeight = height(root->left);
  int rightHeight = height(root->right);
  return std::max(leftHeight, rightHeight) + 1;
}

This code calculates the height of a binary tree by recursively checking left and right subtrees.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Returned	Tree State
1	Start at root	1	-	-	-	1 / \ 2 3 / 4
2	Go left subtree	2	-	-	-	2 / 4
3	Go left subtree	4	-	-	-	4
4	Left child null	null	0	-	0	null
5	Right child null	null	-	0	0	null
6	Return height for node 4	4	0	0	1	4
7	Right child null	null	-	-	0	null
8	Return height for node 2	2	1	0	2	2 / 4
9	Go right subtree	3	-	-	-	3
10	Left child null	null	0	-	0	null
11	Right child null	null	-	0	0	null
12	Return height for node 3	3	0	0	1	3
13	Return height for root node 1	1	2	1	3	1 / \ 2 3 / 4
14	End	-	-	-	-	Height = 3

💡 All nodes visited, recursion unwound, final height returned as 3

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 8	After Step 12	After Step 13	Final
root	Node 1	Node 4	Node 2	Node 1	Node 1	Node 1	null
leftHeight	-	0	1	2	2	2	2
rightHeight	-	-	-	-	1	1	1
heightReturned	-	0	1	2	1	3	3

Key Moments - 3 Insights

Why do we return 0 when the node is null?

Because a null node means no tree exists there, so its height is 0. This is shown in steps 4 and 5 where left and right children are null, returning 0.

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

Adding 1 counts the current node itself. For example, in step 13, max left height is 2 and right height is 1, so height is 3 including the root.

How does recursion help find the height?

Recursion breaks the problem into smaller parts: find height of left and right subtrees first, then combine results. This is visible in steps 2-12 where recursive calls happen.

Visual Quiz - 3 Questions

Look at the execution table, what height is returned for node 4 at step 6?

A 1

B 0

C 2

D 3

💡 Hint

Check the 'Height Returned' column at step 6 in the execution table.

At which step does the recursion return the height for the root node?

A Step 12

B Step 8

C Step 13

D Step 6

💡 Hint

Look for the step where 'Node Visited' is 1 and height returned is final.

If the right subtree of node 1 had height 3 instead of 1, what would be the final height returned?

A 3

B 4

C 2

D 1

💡 Hint

Height is max(leftHeight, rightHeight) + 1; check variable_tracker for how height is computed.

Concept Snapshot

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

Full Transcript

The height of a binary tree is found by starting at the root node and checking if it is null. If null, height is 0. Otherwise, recursively find the height of the left subtree and the right subtree. Then, take the larger of these two heights and add 1 to count the current node. This process continues until all nodes are visited and the maximum height is returned. The execution table shows each step visiting nodes, returning heights for null children as 0, and combining results upwards. Key moments include understanding why null nodes return 0, why we add 1, and how recursion breaks down the problem. The final height for the example tree is 3.

Practice

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

easy

A. 2

B. Undefined

C. 1

D. 0

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 D

4. Quick Check:

   Single node tree height = 0 [OK]

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

Common Mistakes:

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

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

easy

A. int height(Node* root);

B. void height(Node root);

C. int height(Node root);

D. Node height(Node* root);

Solution

1. Step 1: Identify return type

   The height function returns an integer representing height, so return type is int.

2. Step 2: Identify parameter type

   Binary tree nodes are usually passed as pointers to avoid copying, so parameter is Node* root.

3. Final Answer:

   int height(Node* root); -> Option A

4. Quick Check:

   Return int, parameter Node pointer [OK]

Hint: Height returns int, takes pointer to Node [OK]

Common Mistakes:

• Using void return type
• Passing Node by value
• Returning Node instead of int

3. What is the output of the following C++ code snippet?

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

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

int main() {
  Node n1 = {1, nullptr, nullptr};
  Node n2 = {2, nullptr, nullptr};
  Node n3 = {3, &n1, &n2};
  std::cout << height(&n3);
  return 0;
}

medium

A. 3

B. 1

C. 2

D. 0

Solution

1. Step 1: Analyze tree structure

   Root n3 has two children n1 and n2, both leaves with height 1.

2. Step 2: Calculate height recursively

   Height of n1 and n2 is 1, so height of n3 = 1 + max(1,1) = 2.

3. Step 3: Confirm output

   The code prints height(&n3), which is 2.

4. Final Answer:

   2 -> Option C

5. Quick Check:

   Height = 2 [OK]

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

Common Mistakes:

• Counting nodes instead of edges
• Returning 0 for non-empty tree
• Misreading tree structure

4. Identify the error in the following height function for a binary tree:

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

medium

A. Base case should return 0, not -1

B. Function should return Node*, not int

C. Missing check for leaf nodes

D. Incorrect use of ternary operator

Solution

1. Step 1: Check base case return value

   Returning -1 for nullptr causes height to be off by one.

2. Step 2: Correct base case

   Base case should return 0 for empty tree to count height correctly.

3. Final Answer:

   Base case should return 0, not -1 -> Option A

4. Quick Check:

   Base case = 0 for empty tree [OK]

Hint: Base case for empty node returns 0 height [OK]

Common Mistakes:

• Returning -1 causes negative height
• Ignoring nullptr check
• Wrong return type

5. Given a binary tree where some nodes have only one child, what is the height of the tree below?

       10
      /  
     5    
      \   
       7  
        \
         9

hard

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: Trace longest path from root to leaf

   Path is 10 -> 5 -> 7 -> 9, which has 4 nodes and 3 edges.

2. Step 2: Count edges on path

   Counting edges: 10-5 (1), 5-7 (2), 7-9 (3).

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Longest path length = 3 edges [OK]

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

Common Mistakes:

• Counting nodes instead of edges
• Ignoring missing left child
• Assuming height is number of levels with both children