Height of Binary Tree in DSA Python

Mental Model

The height of a binary tree is the longest path from the root to any leaf node. It tells us how tall the tree is.

Analogy: Imagine a family tree where the height is how many generations there are from the oldest ancestor (root) down to the youngest descendant (leaf).

    1
   / \
  2   3
 / 
4  

(Height is the longest path from 1 to 4)

Dry Run Walkthrough

Input: Binary tree: 1 -> 2 -> 4 (left child), 1 -> 3 (right child)

Goal: Find the height of this binary tree

Step 1: Start at root node 1

Node 1 ↑

Why: We begin measuring height from the root

Step 2: Go to left child node 2

1 -> 2 ↑, 3

Why: Check height of left subtree

Step 3: Go to left child node 4

1 -> 2 -> 4 ↑, 3

Why: Go deeper to find longest path

Step 4: Node 4 has no children, height here is 1

Leaf node 4 ↑

Why: Leaf node height is 1

Step 5: Back to node 2, right child is null, so height is max(1,0)+1=2

Node 2 ↑ with left height 1, right height 0

Why: Height at node 2 includes its longest child plus 1

Step 6: Go to right child node 3 of root

1 -> 3 ↑, left subtree height 2

Why: Check height of right subtree

Step 7: Node 3 has no children, height is 1

Leaf node 3 ↑

Why: Leaf node height is 1

Step 8: Back to root node 1, height is max(2,1)+1=3

Root node 1 ↑ with left height 2, right height 1

Why: Height of tree is longest subtree height plus 1

Result:

1 -> 2 -> 4 (height 3)
1 -> 3 (height 3)
Final height: 3

Annotated Code

DSA Python

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

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

# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)

print(height_of_tree(root))

if root is None:

base case: empty subtree has height 0

left_height = height_of_tree(root.left)

recursively find height of left subtree

right_height = height_of_tree(root.right)

recursively find height of right subtree

return max(left_height, right_height) + 1

height is one more than the taller subtree

Output

3

Complexity Analysis

Time: O(n) because we visit every node once to calculate height

Space: O(h) where h is tree height due to recursion stack

vs Alternative: Iterative approaches exist but recursion is simpler and intuitive for tree height

Edge Cases

Empty tree (root is None)

Returns height 0

DSA Python

if root is None:

Tree with only root node

Returns height 1

DSA Python

return max(left_height, right_height) + 1

Unbalanced tree (one side deeper)

Returns height of longest path correctly

DSA Python

return max(left_height, right_height) + 1

When to Use This Pattern

When you need to find the longest path from root to leaf in a tree, use the height calculation pattern with recursion to explore all paths.

Common Mistakes

Mistake: Returning left_height + right_height instead of max of both
Fix: Use max(left_height, right_height) + 1 to get correct height

Mistake: Not handling None nodes as base case
Fix: Add base case if root is None: return 0

Summary

Calculates the longest path from root to leaf in a binary tree.

Use when you want to know how tall or deep a tree is.

The height is one more than the tallest subtree height at each node.

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