Height of Binary Tree in DSA Python - Time & Space Complexity

Time Complexity: Height of Binary Tree

O(n)

Understanding Time Complexity

We want to understand how long it takes to find the height of a binary tree as the tree grows bigger.

The question is: how does the time needed change when the tree has more nodes?

Scenario Under Consideration

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

This code finds the height of a binary tree by checking the height of left and right subtrees recursively.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Recursive calls to visit each node once.
• How many times: Once per node in the tree.

How Execution Grows With Input

As the number of nodes (n) increases, the function visits each node once, so the total work grows directly with n.

Input Size (n)	Approx. Operations
10	About 10 recursive calls
100	About 100 recursive calls
1000	About 1000 recursive calls

Pattern observation: The work grows linearly as the tree size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the height grows directly in proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "The height calculation only takes O(log n) time because the tree height is log n."

[OK] Correct: Even if the height is log n, the function must visit every node to be sure, so it still takes O(n) time.

Interview Connect

Understanding this helps you explain how recursive tree algorithms scale, a key skill for many coding challenges and interviews.

Self-Check

"What if we changed the tree to be a linked list (all nodes have only one child)? How would the time complexity change?"

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