Maximum Depth of a Binary Tree

The depth of a tree is the length of the longest path from the root to a leaf. Recursively, the depth of a node is one plus the larger of the depths of its two subtrees, and an empty subtree has depth zero.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def max_depth(root):
    if root is None:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))


tree = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(5))
print(max_depth(tree))

The output is 3. The longest root to leaf path goes through the node with value 2 and then the node with value 4, which is three nodes deep.

The mechanism is that a node's depth is entirely determined by its deeper child, so the recursion returns the maximum of two smaller subproblems. The base case of an empty subtree is what terminates the recursion, and the plus one accounts for the node itself.

The trade-off to name is the stack. The recursion nests one level per node, so a completely skewed tree with a hundred thousand nodes would exhaust the Python stack, and in a language without a growable stack it would be a crash rather than an exception. The iterative version in the next answer avoids that at the cost of a little more bookkeeping, and it is the version to reach for whenever the tree depth is not bounded by something you control.

Keep a list of the nodes on the current level. At each step, build a new list containing the children of everything in the current list, and count the level. The number of levels you go through is the depth.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def max_depth_iterative(root):
    if root is None:
        return 0
    depth = 0
    level = [root]
    while level:
        next_level = []
        for node in level:
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        level = next_level
        depth += 1
    return depth


tree = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(5))
print(max_depth_iterative(tree))

The output is 3, the same answer as the recursive version. The tree has three levels: the root, its two children, and then the two grandchildren under the left child.

The mechanism is that each pass processes exactly one level. The list of nodes for the level is replaced by the list of their children, so the level structure is preserved explicitly rather than being encoded in the call stack. The loop ends when a level has no children at all, which happens at the deepest leaf.

The trade-off to name is memory against stack safety. This version allocates a new list per level, so the peak memory is the size of the widest level, which for a balanced tree is half the node count. That is more than the recursive version, which uses stack space proportional to the height but only one frame at a time. The recursive version wins on memory for a wide tree and loses for a deep one, so the choice depends on the shape you expect. A depth first search with an explicit stack is the option that keeps the memory proportional to the height instead.

Use an explicit stack that carries the depth of each node rather than relying on the call stack to track it. Push the root with depth one, and whenever you pop a node, update the maximum and push its children with a depth one greater.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def max_depth_deep(root):
    if root is None:
        return 0
    deepest = 0
    stack = [(root, 1)]
    while stack:
        node, depth = stack.pop()
        if depth > deepest:
            deepest = depth
        if node.left:
            stack.append((node.left, depth + 1))
        if node.right:
            stack.append((node.right, depth + 1))
    return deepest


tree = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(5))
print(max_depth_deep(tree))

The output is 3. Each node carries its own depth, so the answer no longer depends on how the frames happen to be nested.

The mechanism is that the stack entry becomes a pair of the node and its depth. The depth is simply the parent depth plus one, so it can be computed at push time without any unwinding. The maximum over all the depths seen is the height of the tree, because the deepest node is a leaf.

The trade-off to name is memory. The explicit stack can hold as many entries as the tree has nodes in the worst case, so it uses more memory than the recursion, whose stack usage is bounded by the height. What it buys is that the memory is on the heap, where it can grow, rather than on a fixed call stack. In practice, when a tree can be untrusted or arbitrarily deep, converting the recursion to an explicit stack is the difference between a service that survives and one that dies on a crafted input.