DSA Maximum Depth of a Binary Tree

The problem

The maximum depth of a binary tree is a count of edges. It counts the edges on the longest path from the root down to a leaf.

A leaf is a node with no children. A path follows child links, always moving down. This article counts edges, so a tree of one node has depth 0, and an empty tree has depth -1.

That convention is a choice, and it is used in every line below. The input is a tree built from nodes with a value, a left child, and a right child. The output is one integer.

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

from collections import deque

def levels(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(row)
    return result

empty = None
single = TreeNode(9)
balanced = TreeNode(4,
                    TreeNode(2, TreeNode(1), TreeNode(3)),
                    TreeNode(6, TreeNode(5), TreeNode(7)))
chain = TreeNode(1, None, TreeNode(2, None, TreeNode(3, None, TreeNode(4, None, TreeNode(5)))))
bent = TreeNode(1, TreeNode(2), TreeNode(3, None, TreeNode(4)))
for label, tree, expected in [("empty", empty, -1), ("single", single, 0), ("balanced", balanced, 2), ("chain of five", chain, 4), ("bent", bent, 2)]:
    print(label, "levels:", levels(tree), "depth:", expected)

Read the level lists as pictures. Each inner list is one level of the tree, from the root down. The balanced tree spreads its seven nodes over three levels, so its depth is 2 edges.

The chain holds fewer nodes and more depth. Its five nodes sit on five levels, one per level, so its depth is 4 edges. Shape, not size, decides this answer.

Intuition: counting nodes gives the wrong winner

A first idea counts the nodes. More nodes feels like a bigger, deeper tree. The count is easy to compute, and it points the wrong way on the cases above.

Depth is about levels, not about how many nodes share those levels. Two children side by side add nodes without adding a single edge to the longest path.

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

from collections import deque

def levels(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        row = []
        for _ in range(len(queue)):
            node = queue.popleft()
            row.append(node.value)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        result.append(row)
    return result

def count_nodes(node):
    if node is None:
        return 0
    return 1 + count_nodes(node.left) + count_nodes(node.right)

balanced = TreeNode(4,
                    TreeNode(2, TreeNode(1), TreeNode(3)),
                    TreeNode(6, TreeNode(5), TreeNode(7)))
chain = TreeNode(1, None, TreeNode(2, None, TreeNode(3, None, TreeNode(4, None, TreeNode(5)))))
for label, tree in [("balanced", balanced), ("chain of five", chain)]:
    print(label, "nodes:", count_nodes(tree), "levels:", len(levels(tree)), "depth in edges:", len(levels(tree)) - 1)

The balanced tree wins the node count, 7 against 5. It loses the depth, 2 against 4. Any method based on counting nodes ranks these two trees in the wrong order.

The level count in the same output does give the depth, minus one. That works, but it builds every level list just to measure one number. A method that works node by node can find the same number without building anything.

Brute force: list every root-to-leaf path

The straightforward method walks every path from the root to a leaf. It records each path in full. The answer is the length of the longest recorded path, minus one for the step from nodes to edges.

Recording whole paths is the wasteful part. The top of the tree appears in every path under it, so its values are copied again and again.

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

visits = 0

def all_paths(node, path, found):
    global visits
    visits += 1
    path = path + [node.value]
    if node.left is None and node.right is None:
        found.append(path)
        return
    if node.left is not None:
        all_paths(node.left, path, found)
    if node.right is not None:
        all_paths(node.right, path, found)

tree = TreeNode(1, TreeNode(2), TreeNode(3, None, TreeNode(4)))
found = []
all_paths(tree, [], found)
for path in found:
    print("path:", path)
print("longest path edges:", max(len(path) for path in found) - 1)
print("node visits:", visits)

The two paths are listed, and the longest has three nodes, so the answer is 2 edges. The answer is right. The method paid for it by storing every path and copying shared prefixes into each one.

One fact points to the cheaper method. Only the length of the longest path matters. A node never needs the paths below it, only the depth of the taller side below it.

The optimal solution: one plus the taller child

Recursion is a function calling itself on smaller inputs. Here the smaller inputs are the two subtrees, the tree under the left child and the tree under the right child.

The key idea is one sentence. The depth of a tree is one plus the depth of its taller child, with an empty tree defined as -1, so each node needs only two numbers from below and keeps the larger one.

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

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

empty = None
single = TreeNode(9)
balanced = TreeNode(4,
                    TreeNode(2, TreeNode(1), TreeNode(3)),
                    TreeNode(6, TreeNode(5), TreeNode(7)))
chain = TreeNode(1, None, TreeNode(2, None, TreeNode(3, None, TreeNode(4, None, TreeNode(5)))))
bent = TreeNode(1, TreeNode(2), TreeNode(3, None, TreeNode(4)))
for label, tree in [("empty", empty), ("single", single), ("balanced", balanced), ("chain of five", chain), ("bent", bent)]:
    print(label, "depth:", max_depth(tree))

All five cases from the start of the article pass. The empty tree returns -1 directly. That one base case is what makes a leaf answer 0, because a leaf adds 1 to the -1 of its taller, empty child.

A missing child is never a special case in the caller. It answers -1 and loses the max comparison against any real child. The bent tree uses exactly that on its node 3, which has only a right child.

Walkthrough: answers rising through the bent tree

Follow the bent tree from the leaves up. Node 2 is a leaf, so it answers 0. Node 4 is also a leaf, and it answers 0.

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

def traced_depth(node):
    if node is None:
        return -1
    left = traced_depth(node.left)
    right = traced_depth(node.right)
    own = 1 + max(left, right)
    print("node", node.value, "left depth:", left, "right depth:", right, "own depth:", own)
    return own

tree = TreeNode(1, TreeNode(2), TreeNode(3, None, TreeNode(4)))
print("answer:", traced_depth(tree))

Node 3 reads -1 from its missing left child and 0 from node 4. The larger value wins, so node 3 answers 1. The missing child cost it nothing.

The root reads 0 from node 2 and 1 from node 3. It adds one and answers 2. That is the depth printed for the bent case in section 1, read off the bottom row of the trace.

Complexity

Time is O(n). The recursion visits each node exactly once and does a fixed amount of work there, one comparison and one addition.

Space is O(h), where h is the depth in edges. The call stack holds one frame per level on the current path, so a balanced tree uses few frames and a chain uses one frame per node.

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

visits = 0

def max_depth(node):
    global visits
    if node is None:
        return -1
    visits += 1
    return 1 + max(max_depth(node.left), max_depth(node.right))

def chain_of(n):
    root = None
    for value in range(n, 0, -1):
        root = TreeNode(value, None, root)
    return root

def balanced_of(values):
    if not values:
        return None
    mid = len(values) // 2
    return TreeNode(values[mid], balanced_of(values[:mid]), balanced_of(values[mid + 1:]))

for label, tree in [("balanced 7", balanced_of([1, 2, 3, 4, 5, 6, 7])), ("balanced 15", balanced_of(list(range(1, 16)))), ("chain 15", chain_of(15))]:
    visits = 0
    depth = max_depth(tree)
    print(label, "depth:", depth, "node visits:", visits)

The visit count equals the node count every time, on both shapes. What changes with shape is the stack. The chain of 15 needs a stack 15 frames deep at its lowest point, and the balanced tree of 15 needs only 4.

Edge cases and pitfalls

An empty tree answers -1 under this convention, and a single node answers 0. A tree that leans all to one side answers one less than its node count, because every node adds exactly one edge to the path.

The convention is the pitfall to watch. Code that returns 0 for an empty tree counts nodes on the longest path instead of edges. Mixing the two conventions in one programme makes every answer differ by one.

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

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

left_chain = TreeNode(1, TreeNode(2, TreeNode(3)))
print("empty:", max_depth(None))
print("single node:", max_depth(TreeNode(9)))
print("left chain of three:", max_depth(left_chain))
print("root with right child only:", max_depth(TreeNode(1, None, TreeNode(2))))
print("root with two leaves:", max_depth(TreeNode(1, TreeNode(2), TreeNode(3))))

A second pitfall is depth itself. The recursion descends once per level, and Python limits how deep recursion may go. A very long chain can reach that limit, so long chains are the shape to test before trusting this code on large inputs. This article never raises that limit.

Taking the smaller child by mistake is a quieter bug. The code would then measure the shortest root-to-leaf path, which is a different quantity. The bent tree exposes it at once, because its two sides answer 0 and 1.