Maximum Depth of Binary Tree

Practice here

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

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Recursive Approach#

• Intuition: The depth of a tree is 1 plus the larger of its left and right subtree depths. This self-similar structure means a recursive solution maps perfectly — each node just asks its children for their depths and returns the maximum plus one.
• Mechanics: The base case returns 0 for a null node. For every non-null node, both children are called recursively; the function then returns 1 + max(leftDepth, rightDepth), naturally accumulating depth as the call stack unwinds back to the root.
• Trade-off: Elegant and concise, but uses O(h) implicit stack space. On a balanced tree this is O(log n), but on a completely skewed tree (effectively a linked list) it degrades to O(n) and can cause stack overflow on very deep inputs.

Analogy: It’s like standing on a floor and saying: “I don’t know how many floors there are below me… let me ask the left staircase and the right staircase. Whichever says more floors, I’ll trust that and add mine.”

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;

        int leftDepth = maxDepth(root->left);
        int rightDepth = maxDepth(root->right);

        return 1 + max(leftDepth, rightDepth);
    }
};

Time Complexity: O(n), Each node visited once

Space Complexity: O(h), Recursion stack,

• Worst Case: O(h) = O(n), Skewed tree
• Best case: O(h) = O(logn), Balanced tree

Iterative Approach#

• Intuition: Level-order traversal (BFS) visits every node level by level; the total number of levels processed equals the maximum depth. Counting completed BFS rounds gives the answer without any recursion.
• Mechanics: A queue is initialised with the root. On each outer iteration the current queue size tells you exactly how many nodes are on the current level — those nodes are dequeued, their children enqueued, and the depth counter incremented once the entire level is drained.
• Trade-off: This approach uses O(n) queue space (worst case: the widest level of the tree), which can be larger than the O(h) stack of the recursive solution for balanced trees. However, it avoids recursion entirely and handles arbitrarily deep trees without risk of stack overflow.

Analogy: Let’s explore the building floor by floor, moving everyone on the current floor to the next floor all together. Each time we finish a floor, we increase the floor count.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root)
            return 0;

        queue<TreeNode*> q;
        q.push(root);
        int depth = 0;

        while(!q.empty())
        {
            
            int size = q.size();
            for(int i=0;i<size;i++)
            {
                TreeNode* currNode = q.front();
                q.pop();

                if(currNode->left)
                    q.push(currNode->left);
                if(currNode->right)
                    q.push(currNode->right);
            }
            depth++;
        }
        return depth;
    }
};

Time Complexity: O(n), Each node visited once

Space Complexity: O(n)

• Worst Case: In the worst case, the queue can store all the nodes of the last level.