Height of Binary Tree in DSA Go - 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

↓

Height = max(left, right) + 1

↓

Return height

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

Execution Sample

DSA Go

func height(node *Node) int {
  if node == nil {
    return 0
  }
  leftHeight := height(node.Left)
  rightHeight := height(node.Right)
  if leftHeight > rightHeight {
    return leftHeight + 1
  }
  return rightHeight + 1
}

This function calculates the height of a binary tree by recursively checking left and right subtree heights.

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Computed	Tree State
1	Start at root	10	-	-	-	10 / \ 5 15 / \ \ 3 7 20
2	Go left	5	-	-	-	Subtree rooted at 5
3	Go left	3	-	-	-	Leaf node 3
4	Node 3 is leaf	3	0	0	1	3
5	Go right	7	-	-	-	Leaf node 7
6	Node 7 is leaf	7	0	0	1	7
7	Compute height at 5	5	1	1	2	5 / \ 3 7
8	Go right	15	-	-	-	Subtree rooted at 15
9	Go left	nil	-	-	-	Empty subtree
10	Left height at 15	nil	0	-	-	-
11	Go right	20	-	-	-	Leaf node 20
12	Node 20 is leaf	20	0	0	1	20
13	Compute height at 15	15	0	1	2	15 \ 20
14	Compute height at root 10	10	2	2	3	10 / \ 5 15 / \ \ 3 7 20
15	Return final height	-	-	-	3	Complete tree height is 3

💡 All nodes visited, heights computed bottom-up, final height returned.

Variable Tracker

Variable	Start	After Step 4	After Step 6	After Step 7	After Step 12	After Step 13	After Step 14	Final
node	10	3	7	5	20	15	10	-
leftHeight	-	0	0	1	0	0	2	-
rightHeight	-	0	0	1	0	1	2	-
height	-	1	1	2	1	2	3	3

Key Moments - 3 Insights

Why do we return 0 when the node is nil?

Because a nil node means no tree exists there, so its height is 0. This is shown in steps 3, 9, and 10 where nil nodes return 0 height.

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

We add 1 to count the current node itself. Steps 7, 13, and 14 show height computed as max(leftHeight, rightHeight) + 1.

How does recursion ensure all nodes are visited?

The function calls itself on left and right children until it reaches nil nodes (steps 3, 9). This bottom-up approach ensures every node's height is computed.

Visual Quiz - 3 Questions

Look at the execution table at step 7, what is the height computed for node 5?

A 1

B 2

C 3

D 0

💡 Hint

Check the 'Height Computed' column at step 7 in the execution table.

At which step does the function return height for the leaf node 20?

A Step 6

B Step 12

C Step 14

D Step 4

💡 Hint

Look for the step where node 20 is visited and height is computed in the execution table.

If the right subtree of node 15 was empty, what would be the height computed at node 15?

A 1

B 0

C 2

D 3

💡 Hint

Refer to steps 10 and 13 where left or right subtree heights are 0 and how height is computed.

Concept Snapshot

Height of Binary Tree:
- Base case: nil node height = 0
- Recursively find left and right subtree heights
- Height = max(leftHeight, rightHeight) + 1
- Counts edges from root to deepest leaf
- Uses post-order traversal (bottom-up)

Full Transcript

To find the height of a binary tree, start at the root node. If the node is nil, return 0 because there is no tree there. Otherwise, recursively find the height of the left subtree and the right subtree. Then, take the maximum of these two heights and add 1 to count the current node. This process continues until all nodes are visited and their heights computed. The final returned value is the height of the entire tree. This method uses a bottom-up approach, visiting leaf nodes first and moving up to the root.