Height of Binary Tree in DSA Python - Execution Trace

Concept Flow - Height of Binary Tree

Start at root node

↓

Is node None?

Yes→Return 0

No↓

Compute height of left subtree

↓

Compute height of right subtree

↓

Height = max(left, right) + 1

↓

Return height

The height is found by recursively checking left and right subtrees, then taking the larger height plus one for the current node.

Execution Sample

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def height(root):
    if root is None:
        return 0
    left_height = height(root.left)
    right_height = height(root.right)
    return max(left_height, right_height) + 1

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

Execution Table

Step	Operation	Node Visited	Left Height	Right Height	Height Computed	Tree State
1	Visit root	1	-	-	-	1 ├─2 └─3
2	Visit left child	2	-	-	-	1 ├─2 └─3
3	Visit left.left (None)	None	0	0	0	1 ├─2 └─3
4	Visit left.right (None)	None	0	0	0	1 ├─2 └─3
5	Compute height at node 2	2	0	0	1	1 ├─2 └─3
6	Visit right child	3	-	-	-	1 ├─2 └─3
7	Visit right.left (None)	None	0	0	0	1 ├─2 └─3
8	Visit right.right (None)	None	0	0	0	1 ├─2 └─3
9	Compute height at node 3	3	0	0	1	1 ├─2 └─3
10	Compute height at root	1	1	1	2	1 ├─2 └─3
11	Return final height	1	1	1	2	1 ├─2 └─3

💡 All nodes visited; height computed as max of left and right subtree heights plus one.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 6	After Step 9	After Step 10	Final
root	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)
left_height	-	Pending	1	1	1	1	1
right_height	-	-	-	Pending	1	1	1
height	-	Pending	Pending	Pending	Pending	2	2

Key Moments - 3 Insights

Why do we return 0 when the node is None?

Returning 0 for None nodes (leaf children) means the height below a leaf is zero, as shown in steps 3, 4, 7, and 8 in the execution_table.

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

Adding 1 accounts for the current node's level, making the height include this node, as seen in steps 5, 9, and 10.

How does recursion ensure all nodes are visited?

The function calls itself on left and right children until None is reached, ensuring every node is processed, demonstrated by the sequence of steps 2 to 9.

Visual Quiz - 3 Questions

Look at the execution_table, what is the height computed at node 2 (step 5)?

A 2

B 0

C 1

D None

💡 Hint

Check the 'Height Computed' column at step 5 in the execution_table.

At which step does the condition 'node is None' first return true?

A Step 6

B Step 3

C Step 2

D Step 1

💡 Hint

Look for the first step where 'Node Visited' is None in the execution_table.

If the right subtree of root had height 2 instead of 1, what would be the final height?

A 3

B 2

C 1

D 4

💡 Hint

Final height is max(left_height, right_height) + 1; see variable_tracker for height calculation.

Concept Snapshot

Height of Binary Tree:
- Height is max height of left and right subtrees plus 1
- Base case: height of None node is 0
- Use recursion to visit all nodes
- Height counts nodes from root to deepest leaf
- Returns 0 for empty tree

Full Transcript

To find the height of a binary tree, start at the root node. If the node is None, return 0 because there is no tree. 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 count the current node's level. This process continues until all nodes are visited. The final height is returned at the root. This method ensures every node contributes to the height calculation.

Practice

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

easy

A. 2

B. 0

C. Undefined

D. 1

Solution

1. Step 1: Understand height definition

   The height of a binary tree is the number of nodes 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 1.

3. Final Answer:

   1 -> Option D

4. Quick Check:

   Height of single node tree = 1 [OK]

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

Common Mistakes:

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

2. Which of the following is the correct Python function header to calculate the height of a binary tree node named root?

easy

A. def height(root, node):

B. def height(root):

C. def height():

D. def height(tree_root):

Solution

1. Step 1: Identify function parameter

   The function needs one parameter representing the root node of the tree.

2. Step 2: Match parameter name and count

   def height(root): uses one parameter named root, which matches the question context.

3. Final Answer:

   def height(root): -> Option B

4. Quick Check:

   One parameter named root is correct [OK]

Hint: Function needs one parameter: the root node [OK]

Common Mistakes:

• Adding extra parameters unnecessarily
• No parameters in function
• Using unrelated parameter names

3. What will be the output of the following code snippet?

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def height(root):
    if root is None:
        return 0
    left_height = height(root.left)
    right_height = height(root.right)
    return max(left_height, right_height) + 1

root = Node(10)
root.left = Node(20)
root.right = Node(30)
root.left.left = Node(40)
print(height(root))

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Trace tree structure

   The tree has root 10, with left child 20 and right child 30. Node 20 has left child 40. The longest path is 10 -> 20 -> 40.

2. Step 2: Calculate height recursively

   Height is max height of left and right subtree plus 1. Left subtree height is 2 (20 -> 40), right subtree height is 1 (30). So total height = max(2,1)+1 = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Longest path length = 3 [OK]

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

Common Mistakes:

• Counting edges instead of nodes
• Ignoring one subtree height
• Returning wrong base case value

4. Find the error in this height calculation function and choose the correct fix:

def height(root):
    if root is None:
        return -1
    left_height = height(root.left)
    right_height = height(root.right)
    return max(left_height, right_height) + 1

medium

A. Add else before recursive calls

B. Change max to min in return statement

C. Change base case return from -1 to 0

D. Remove +1 from return statement

Solution

1. Step 1: Understand base case meaning

   Height of empty tree (None) should be 0, not -1, to count nodes properly.

2. Step 2: Fix base case return value

   Changing return -1 to return 0 fixes height calculation to count nodes correctly.

3. Final Answer:

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

4. Quick Check:

   Base case height = 0 for empty tree [OK]

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

Common Mistakes:

• Returning -1 causes height off by one
• Using min instead of max
• Forgetting to add 1 after recursion

5. Given a binary tree where each node has a value, write a function to find the height of the tree but only counting nodes with even values. What will be the height of this tree?

    2
   / \
  3   4
     / \
    6   7
   /
  8

hard

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Identify even-valued nodes in tree

   Nodes with even values: 2 (root), 4, 6, 8. Nodes 3 and 7 are odd and ignored.

2. Step 2: Calculate height counting only even nodes

   Longest path with even nodes is 2 -> 4 -> 6 -> 8, but since 4 has children 6 and 7, and 7 is odd, it is ignored. The path length counting only even nodes is 4 nodes, but the height counts edges between nodes, so height is 3.

3. Step 3: Clarify height definition for this problem

   Height counts number of edges on longest path with even values only. The path is 2 -> 4 -> 6 -> 8, which has 3 edges, so height is 3.

4. Final Answer:

   3 -> Option A

5. Quick Check:

   Longest even-valued path edge count = 3 [OK]

Hint: Count only even nodes on longest root-to-leaf path, height = edges count [OK]

Common Mistakes:

• Counting odd nodes by mistake
• Confusing edges with nodes
• Ignoring subtree with even nodes