Maximum Depth of Binary Tree – 3 Approaches Explained (DFS, BFS & Stack)

Maximum Depth of Binary Tree (LeetCode 104)

When I started solving tree problems, I had absolutely no idea how to approach them. This was my first tree problem, so I initially watched a YouTube video to understand the intuition. After that, I explored three different ways to solve the problem. In this post, I’ll explain all three approaches in a simple and beginner-friendly manner.

📌 Problem Statement

Given the root of a binary tree, return its maximum depth.

Maximum Depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

🧠 Approach 1: Recursive Depth-First Search (DFS)

This is the most natural way to solve tree problems because trees are recursive by nature. For every node, we calculate the depth of its left and right subtrees and take the maximum.

class Solution:
    def maxDepth(self, root):
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left),
                       self.maxDepth(root.right))

Explanation:

If the node is None, the depth is 0.
Otherwise, compute the depth of left and right subtrees.
Add 1 for the current node.

This approach is clean, intuitive, and easy to write. However, it relies on recursion, which may cause stack overflow for very deep trees.

🧠 Approach 2: Breadth-First Search (Level Order Traversal)

In this approach, we traverse the tree level by level using a queue. Each iteration of the loop processes one complete level of the tree.

from collections import deque

class Solution:
    def maxDepth(self, root):
        if not root:
            return 0

        level = 0
        q = deque([root])

        while q:
            for _ in range(len(q)):
                node = q.popleft()
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            level += 1

        return level

Explanation:

The queue stores nodes of the current level.
The inner loop processes all nodes at that level.
After finishing a level, we increment the depth counter.

This method avoids recursion and works well when dealing with level-based tree problems.

🧠 Approach 3: Iterative DFS Using a Stack

This approach mimics recursion manually using a stack. Each stack entry stores the node along with its current depth.

class Solution:
    def maxDepth(self, root):
        if not root:
            return 0

        level = 0
        stack = [[root, 1]]

        while stack:
            node, current_level = stack.pop()
            level = max(level, current_level)

            if node.left:
                stack.append([node.left, current_level + 1])
            if node.right:
                stack.append([node.right, current_level + 1])

        return level

Explanation:

Each stack element keeps track of the node and its depth.
We update the maximum depth whenever we visit a node.
This avoids recursion while still performing DFS.

This approach is useful when recursion depth might be a concern and gives full control over traversal.

📊 Comparison of All Three Approaches

Approach	Technique	Data Structure	Extra Space	Notes
Recursive DFS	Depth-First Search	Call Stack	O(height)	Clean and intuitive, but uses recursion
BFS	Level Order Traversal	Queue	O(width)	Best for level-based problems
Iterative DFS	Depth-First Search	Stack	O(height)	Avoids recursion, interview-friendly

Road2Geeks

Search This Blog