{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Maximum Depth of Binary Tree – Solution & Complexity

Interview solutions
/
Maximum Depth of Binary Tree

1. Understand the Goal

  • Depth means the number of nodes on a path, counting both the root and the leaf.
  • A single node has depth 1; an empty tree has depth 0.
  • The maximum depth is the longest such path over every leaf in the tree.

2. Break It Into Subproblems

  • The depth of a tree rooted at node is 1 (for node itself) plus the deeper of its two subtrees.
  • Each subtree is itself a smaller binary tree, so the same rule applies recursively.
  • The base case is a missing node (None), which contributes depth 0.

3. Write the Recursive Case

  • Recursively compute the depth of the left subtree and the right subtree.
  • Take the larger of the two, then add 1 for the current node.
def max_depth(root):
    if root is None:
        return 0
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    return 1 + max(left_depth, right_depth)

4. Confirm Complexity

  • Every node is visited exactly once, so time complexity is O(n).
  • The recursion depth matches the tree's height, so space complexity is O(h) for the call stack — O(log n) for a balanced tree, O(n) worst case for a completely skewed tree.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def max_depth(root: TreeNode) -> int:
    if root is None:
        return 0
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    return 1 + max(left_depth, right_depth)

5. Alternative: Iterative Level-Order Traversal

  • Instead of recursing, process the tree level by level with a queue (breadth-first search).
  • Each iteration of the outer loop drains exactly one full level from the queue and enqueues the next level's nodes.
  • Count how many levels are processed before the queue empties — that count is the maximum depth.
  • This avoids growing the call stack, trading it for an explicit queue whose size is bounded by the tree's widest level.
from collections import deque

def max_depth(root: TreeNode) -> int:
    if root is None:
        return 0
    depth = 0
    queue = deque([root])
    while queue:
        depth += 1
        for _ in range(len(queue)):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return depth

FAQ

See also

Practice Maximum Depth of Binary Tree online (run code in the browser)Invert Binary Tree solution (easy)Same Tree solution (easy)Lowest Common Ancestor of a BST solution (medium)Validate Binary Search Tree solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?