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.