Maximum Depth of Binary Tree | Explained with Examples

How to calculate the maximum depth of binary tree with simple Python recursion. This beginner-friendly article breaks down the “why” and “how,” complete with code, walkthrough, and complexity analysis. You can solve the question from this Leetcode 104 – [Problem Link].

Why Tree Height Matters

The height of a binary tree is the number of nodes along the longest path from the root down to a leaf. In algorithmic terms, it’s also called the maximum depth. Knowing the height is fundamental because:

• It tells you how balanced (or skewed) your tree is.
• Many operations (insert, delete, search) depends on tree height for efficiency.

We’ll use simple recursion and Python. By the end, you’ll see how a few lines of code can measure your tree’s height in O(N) time.

Also read about the Program to Find Diameter of a Binary Tree.

Recursive Solution

1. Intuition & Approach

1. Base Case (Empty Tree):
   • If a node is None, its height is 0.
2. Recursive Case:
   • Compute the height of the left subtree.
   • Compute the height of the right subtree.
   • The height at the current node is 1 + max(leftHeight, rightHeight).
3. Why It Works:
   • You’re essentially asking each subtree “how tall are you?” and adding one for the current node.

2. Code Implementation

class Solution:
    def solve(self, node):
        # 1. Base case: an empty subtree has height 0
        if node is None:
            return 0
        
        # 2. Recurse on left and right
        leftHeight  = self.solve(node.left)
        rightHeight = self.solve(node.right)
        
        # 3. Current node’s height = 1 + taller subtree
        return 1 + max(leftHeight, rightHeight)

    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.solve(root)

3. Code Explanation

• solve(node)
  • If node is None, return 0.
  • Otherwise,
    • Recursively get leftHeight from node.left.
    • Recursively get rightHeight from node.right.
    • Return 1 + max(leftHeight, rightHeight).
• maxDepth(root) just kicks off the recursion at the tree’s root.

This compact recursion mirrors the definition of tree height itself—a beautiful alignment of concept and code!

4. Dry Run

Given this tree:

      1
     / \
    2   3
   /     \
  4       5
           \
            6

• At node 4 → both children None → height = 1 + max(0,0) = 1.
• At node 2 → left=1 (from 4), right=0 → height = 1 + max(1,0) = 2.
• At node 6 → height = 1.
• At node 5 → left=0, right=1 → height = 2.
• At node 3 → left=0, right=2 → height = 3.
• At root (1) → left=2, right=3 → height = 1 + max(2,3) = 4.

So the tree’s height is 4.

5. Time & Space Complexity

• Time Complexity:
  • You visit each node exactly once → O(N) for N nodes.
• Space Complexity:
  • O(H) recursion call stack, where H is the tree height.
  • In the worst (skewed) case H ≈ N → O(N); in a balanced tree H ≈ log N.

Iterative Solution

We all know the recursive trick to find a tree’s height: dive left, dive right, take the bigger, and add one. But what if you preferred an iterative approach, no function call stack, just a good old queue? That’s where breadth-first search (BFS) or level-order traversal comes.

By walking the tree level by level, you can count how many “floors” it has. Each time you finish processing one level, you increase the height by one.

1. Intuition & Approach

1. Use a queue to hold nodes at the current level.
2. Initialize height = 0.
3. While the queue isn’t empty:
   • Note how many nodes are on this level (level_size = len(queue)).
   • Process exactlylevel_size nodes:
     • Dequeue a node, enqueue its children (if any).
   • After processing those nodes, you’ve completed one level, increment height.
4. Stop when there are no more levels (queue is empty); height now holds the tree’s maximum depth.

This approach guarantees you visit every node exactly once—O(N) time—and your queue never holds more nodes than one full level—O(W) space, where W is the maximum width.

2. Code Implementation

from collections import deque

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # If the tree is empty, its height is 0
        if not root:
            return 0

        queue = deque([root])
        height = 0

        # Process level by level
        while queue:
            level_size = len(queue)
            height += 1  # we’re about to process one more level

            # Dequeue all nodes in the current level, enqueue their children
            for _ in range(level_size):
                node = queue.popleft()
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        return height

3. Dry Run Example

      1
     / \
    2   3
   /     \
  4       5

• Start: queue = [1], height = 0
• Loop 1:
  • level_size = 1, height = 1
  • Pop 1, enqueue [2, 3]
• Loop 2:
  • queue = [2, 3], level_size = 2, height = 2
  • Pop 2 → enqueue [4]; pop 3 → enqueue [4, 5]
• Loop 3:
  • queue = [4, 5], level_size = 2, height = 3
  • Pop 4 (no children), pop 5 (no children) → queue = []
• End: queue is empty, return height = 3

So the tree has 3 levels:

1. node 1, 2) nodes 2 & 3, 3) nodes 4 & 5.

4. Time & Space Complexity

• Time: O(N) — you touch each node once.
• Space: O(W) — at most one level’s worth of nodes in the queue (worst-case W ≈ N/2).

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.