Height of Binary Tree in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the height of this binary tree?

Consider the following binary tree structure and code to find its height. What will be the printed height?

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 1 + max(left_height, right_height)

# Constructing the tree
root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.right = Node(18)

print(height(root))

A 3

B 2

C 4

D 5

💡 Hint

Height counts the number of nodes along the longest path from root to leaf.

The longest path is from root (10) to leaf (3 or 7 or 18) which has 3 nodes, so height is 3.

❓ Predict Output

intermediate

What is the height after adding a new node?

Given the same height function, what is the height after adding a new node as the left child of node 3?

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 1 + max(left_height, right_height)

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.right = Node(18)
root.left.left.left = Node(1)  # New node added here

print(height(root))

A 4

B 5

C 3

D 2

💡 Hint

Adding a node deeper on the left subtree increases height by 1.

The longest path is now 10 -> 5 -> 3 -> 1, which has 4 nodes, so height is 4.

🔧 Debug

advanced

What error does this code raise?

What error will this code raise when trying to compute the height of the tree?

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 1 + max(left_height, right_height)

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(3)
root.left.right = Node(7)
root.right.right = Node(18)
root.left.left.left = 1  # Incorrect assignment

print(height(root))

A RecursionError: maximum recursion depth exceeded

B TypeError: unsupported operand type(s) for max()

C AttributeError: 'int' object has no attribute 'left'

D No error, prints 4

💡 Hint

Check the type of the left child of node 3.

Assigning an integer instead of a Node causes height(root.left.left.left) to call height(1), which fails when accessing 1.left.

🧠 Conceptual

advanced

How does height change with a skewed tree?

Consider a binary tree where every node has only a right child, forming a chain of 7 nodes. What is the height of this tree?

A 0

B 1

C 3

D 7

💡 Hint

Height counts nodes along the longest path from root to leaf.

Since the tree is a chain of 7 nodes, height is 7.

🚀 Application

expert

What is the height after multiple insertions?

Starting with an empty tree, nodes are inserted in this order: 10, 5, 15, 3, 7, 18, 1, 0. Using the height function, what is the height after all insertions?

DSA Python

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

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

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

root = None
for v in [10, 5, 15, 3, 7, 18, 1, 0]:
    root = insert(root, v)

print(height(root))

A 7

B 5

C 6

D 4

💡 Hint

Trace the longest path from root to leaf after all insertions.

The longest path is 10 -> 5 -> 3 -> 1 -> 0, which has 5 nodes, so height is 5.

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