Introduction

Recursion works well for binary-tree depth because the structure of the problem matches the structure of the data. The depth of a tree depends on the depths of its left and right subtrees, so a function can solve the whole problem by calling itself on those smaller trees.

The key to understanding the algorithm is not magic self-calling. It is the combination of a base case that stops at an empty node and a recursive case that asks the same question of each child.

The Recursive Idea

For a node in a binary tree:

• if the node is empty, its depth is 0,
• otherwise, its depth is 1 + max(depth(left), depth(right)).

That is the entire algorithm.

The recursive function does not need to know the whole tree in advance. At each node, it reduces the problem to two smaller subproblems, one for each child.

A Concrete Python Example

1class Node:
2    def __init__(self, value, left=None, right=None):
3        self.value = value
4        self.left = left
5        self.right = right
6
7
8def depth(node):
9    if node is None:
10        return 0
11
12    left_depth = depth(node.left)
13    right_depth = depth(node.right)
14    return 1 + max(left_depth, right_depth)
15
16
17tree = Node(
18    10,
19    left=Node(5, left=Node(2)),
20    right=Node(20, right=Node(30))
21)
22
23print(depth(tree))

This prints 3 because the longest path from the root to a leaf has three nodes.

How the Calls Unfold

Suppose the function starts at the root:

1. It cannot answer immediately, so it asks for the depth of the left subtree.
2. That call may ask for the depth of its own left and right children.
3. Eventually the recursion reaches a missing child, where the base case returns 0.
4. Then the stack unwinds and each parent computes its result from the child results.

The important idea is that recursive calls go down the tree, but the actual depth values are assembled on the way back up.

For a leaf node:

• 'depth(None) on the left returns 0'
• 'depth(None) on the right returns 0'
• so the leaf returns 1 + max(0, 0) = 1

That result becomes input to its parent, and the process continues upward.

Why the Base Case Matters

The base case is what stops the recursion:

if node is None:
    return 0

Without this condition, the function would keep trying to recurse past the end of the tree and never finish correctly. The base case is also what defines the depth of an empty tree.

Once that is in place, every non-empty node has a well-defined answer built from smaller answers.

Time and Space Complexity

Each node is visited once, so the time complexity is O(n) for a tree with n nodes.

The extra space comes from the call stack. That is O(h), where h is the height of the tree:

• 'O(log n) for a balanced tree,'
• 'O(n) for a highly skewed tree.'

So the recursive algorithm is efficient, but the shape of the tree affects stack depth.

Common Pitfalls

• Forgetting the base case for None, which breaks the recursion immediately.
• Confusing depth measured in nodes with depth measured in edges. You need one definition and must use it consistently.
• Thinking recursion computes the whole answer while moving downward. The final value is actually assembled during the return phase.
• Using recursion on extremely deep skewed trees without considering stack depth limits.
• Returning min(left, right) instead of max(left, right), which computes the shallowest path instead of the deepest one.

Summary

• The depth of a binary tree is defined recursively from the depths of its children.
• The base case returns 0 for an empty node.
• Each non-empty node returns 1 + max(left_depth, right_depth).
• Recursive calls go down the tree, and the real answer is built as the stack unwinds.
• The algorithm runs in O(n) time with O(h) call-stack space.