{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Maximum Depth of Binary Tree – Solution & Complexity

Interview solutions
/
Maximum Depth of Binary Tree

Solution Walkthrough

  1. Step 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. Step 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. Step 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. Step 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. Step 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
Learn the Tree Traversal pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Maximum Depth of Binary Tree online (run code in the browser)Balanced Binary Tree solution (easy)Binary Tree Inorder Traversal solution (easy)Binary Tree Postorder Traversal solution (easy)Binary Tree Preorder Traversal solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?