Maximum Depth of a Binary Tree

When an interviewer asks for the maximum depth of a binary tree, they are not really testing if you know what “depth” means. They want to see if you can think about a tree the way it is actually built. A tree is a small piece that contains more small pieces just like it. So this question is a quiet test of recursion. If you can see the tree as “a node sitting on top of two smaller trees”, you have already solved it.

Let us walk through it the way you would in the room.

🌳 The Problem

You are given the root of a binary tree. A binary tree is a structure where every node has at most two children: a left child and a right child. You need to return its maximum depth.

The maximum depth is the number of nodes on the longest path going from the root down to the farthest leaf. A leaf is a node with no children. An empty tree has depth 0.

Here is a small example:

Input:
        3
       / \
      9   20
         /  \
        15   7

Output: 3

See why the answer is 3? The longest path is 3 → 20 → 15 (or 3 → 20 → 7). That path touches 3 nodes. The path on the left, 3 → 9, touches only 2 nodes. So the deepest one wins, and the answer is 3.

🤔 The Simple Idea First

One way people first think about this is to walk the whole tree and keep a counter of “how deep am I right now”. Then you track the biggest value of that counter. That works, but you have to carry an extra depth variable down through every call. You also have to remember to update a separate maximum. It is easy to make a mistake here, and in an interview you can lose track of the values.

There is a cleaner way to say the same thing. Instead of pushing a counter downward, let each node ask its children “how deep are you?” and build the answer coming back up.

✅ The Recursive Approach

Here is the key thought. The depth of any node is just 1 plus the depth of its taller child. The 1 is for the node itself. Then you add whichever side goes deeper, the left subtree or the right subtree.

And what about an empty spot, where there is no node at all? Its depth is 0. That is the base case that stops the recursion. So the whole rule fits in two lines:

• If the node is empty (null), return 0.
• Otherwise return 1 + max(depth(left), depth(right)).

That is it. Every node solves a tiny version of the same problem, and the answers stack up to give the full height.

Steps to find the maximum depth

1. Start at the root node.
2. If the current node is null, return 0. This is the base case.
3. Recursively find the depth of the left subtree.
4. Recursively find the depth of the right subtree.
5. Take the larger of the two depths.
6. Add 1 for the current node and return that value.

Let us build the example tree and print its depth.

#include <stdio.h>
#include <stdlib.h>

// A node of the binary tree
struct Node {
    int val;
    struct Node *left;
    struct Node *right;
};

// Helper to create a new node
struct Node* newNode(int val) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Bigger of two numbers
int max(int a, int b) {
    return a > b ? a : b;
}

// Depth = 1 + taller child's depth; empty node is 0
int maxDepth(struct Node* root) {
    if (root == NULL) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

int main() {
    // Build the tree:    3 / (9, 20) / (15, 7)
    struct Node* root = newNode(3);
    root->left = newNode(9);
    root->right = newNode(20);
    root->right->left = newNode(15);
    root->right->right = newNode(7);

    printf("Maximum depth: %d\n", maxDepth(root));
    return 0;
}

Maximum depth: 3

#include <iostream>
#include <algorithm>
using namespace std;

// A node of the binary tree
struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

// Depth = 1 + taller child's depth; empty node is 0
int maxDepth(Node* root) {
    if (root == nullptr) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

int main() {
    // Build the tree:    3 / (9, 20) / (15, 7)
    Node* root = new Node(3);
    root->left = new Node(9);
    root->right = new Node(20);
    root->right->left = new Node(15);
    root->right->right = new Node(7);

    cout << "Maximum depth: " << maxDepth(root) << endl;
    return 0;
}

Maximum depth: 3

public class MaxDepth {

    // A node of the binary tree
    static class Node {
        int val;
        Node left, right;
        Node(int val) { this.val = val; }
    }

    // Depth = 1 + taller child's depth; empty node is 0
    static int maxDepth(Node root) {
        if (root == null) return 0;
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }

    public static void main(String[] args) {
        // Build the tree:    3 / (9, 20) / (15, 7)
        Node root = new Node(3);
        root.left = new Node(9);
        root.right = new Node(20);
        root.right.left = new Node(15);
        root.right.right = new Node(7);

        System.out.println("Maximum depth: " + maxDepth(root));
    }
}

Maximum depth: 3

# A node of the binary tree
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

# Depth = 1 + taller child's depth; empty node is 0
def max_depth(root):
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

# Build the tree:    3 / (9, 20) / (15, 7)
root = Node(3)
root.left = Node(9)
root.right = Node(20)
root.right.left = Node(15)
root.right.right = Node(7)

print("Maximum depth:", max_depth(root))

Maximum depth: 3

// A node of the binary tree
class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

// Depth = 1 + taller child's depth; empty node is 0
function maxDepth(root) {
  if (root === null) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

// Build the tree:    3 / (9, 20) / (15, 7)
const root = new Node(3);
root.left = new Node(9);
root.right = new Node(20);
root.right.left = new Node(15);
root.right.right = new Node(7);

console.log("Maximum depth:", maxDepth(root));

Maximum depth: 3

⏱️ Time and Space Complexity

We visit every node exactly once, so time is O(n) where n is the number of nodes. The space comes from the recursion call stack, which goes as deep as the height of the tree.

Here h is the height of the tree. In the worst case the tree is one long slanted chain, so h equals n and the space becomes O(n). For a balanced tree h is much smaller, about log n.

🧩 Key Takeaways

• ✅ The depth of a node is 1 + max(left depth, right depth). The empty node returns 0 and stops the recursion.
• ✅ Let recursion return answers up the stack instead of passing a counter down. It is cleaner and easier to reason about.
• ✅ Time is O(n) because every node is visited once.
• ✅ Space is O(h), the height of the tree, because of the recursion stack. A skewed tree pushes this to O(n).
• ✅ If depth could be huge, an iterative BFS or stack-based version avoids stack overflow.

🚀 What’s Next?

• Invert a Binary Tree
• Height of a Tree