ToolMight LogoToolMight
EasyTrees & BSTPattern: Depth-First Search (DFS)Pattern: Breadth-First Search (BFS)Pattern: Tree Recursion

Maximum Depth of Binary Tree

Find the maximum depth (height) of a binary tree along the longest path from root to leaf. The quintessential problem for learning bottom-up divide-and-conquer tree recursion.

Problem Statement

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Examples & Constraints

Example 1
Input: root = [3, 9, 20, null, null, 15, 7]
Output: 3
Explanation: The longest root-to-leaf path is 3 -> 20 -> 15 (or 7), which contains 3 nodes.
Example 2
Input: root = []
Output: 0
Explanation: An empty tree has a maximum depth of 0.
Constraints
  • The number of nodes in the tree is in the range [0, 10^4].
  • -100 <= Node.val <= 100

Recursive DFS (Divide & Conquer)

Optimal Approach
Time:O(n)
Space:O(h)

Recursively find the height of the left and right subtrees. The tree height is 1 + max(leftHeight, rightHeight).

Time ComplexityO(n)

Every node in the binary tree of size N is visited exactly once.

Space ComplexityO(h)

Consumes memory on the call stack proportional to tree height H: O(log n) for a balanced tree, and O(n) for a completely skewed linked-list tree.

Underlying algorithmic logic

The Bottom-Up Recurrence Relation

A tree problem can almost always be broken down into identical subproblems on its subtrees:

  1. Base Case: If root == null, an empty tree has height 0.
  2. Recursive Hypothesis:
  • Let leftDepth = maxDepth(root.left).
  • Let rightDepth = maxDepth(root.right).
  1. Combine Step:
  • The current node contributes 1 level of depth to whatever is the taller branch below it.
  • Return 1 + max(leftDepth, rightDepth).

Call Stack Lifecycle

Execution flows down to the leaf nodes first (post-order traversal: Left, Right, then Root). When the leaves return depth 1, their parents calculate 1 + 1 = 2, bubbling up heights to the root.

Step-by-step execution walkthrough

1
Root Node (3)

Inspect root (3). Delegate subtrees: maxDepth(9) and maxDepth(20).

root = 3 (waiting on children)
2
Left Leaf Node (9)

Both children of 9 are null. maxDepth(null) returns 0. Depth of 9 is 1 + max(0, 0) = 1.

leftSubtreeDepth = 1
3
Right Subtree (20)

Node 20 inspects children 15 and 7. Both are leaves of depth 1. Depth of 20 is 1 + max(1, 1) = 2.

rightSubtreeDepth = 2
4
Root Combination

Combine at root 3: 1 + max(1, 2) = 3.

Result: 3
Advantages
  • •Extremely clean and concise code
  • •Natural divide-and-conquer recurrence structure
Trade-offs
  • •Risk of call stack overflow on deeply degenerate/skewed trees (N > 10,000)

Code Implementations

Copy & paste production-ready solutions for Recursive DFS (Divide & Conquer) in your language of choice

File: solution.py
Python
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 | None) -> int:
    if not root:
        return 0
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    return 1 + max(left_depth, right_depth)
if __name__ == "__main__":
    # Tree: [3, 9, 20, null, null, 15, 7]
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print("Maximum Depth:", max_depth(root))
Interactive visualizer available

Understand Binary Search Tree Visually

Explore hierarchical parent-child nodes, traversal modes (in-order, pre-order, post-order), and search lookups. Test live edge cases and watch memory state transitions step-by-step.

Launch Binary Search Tree Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyTrees & BST
Visualizer

Invert Binary Tree

Mirror-flip a binary tree so every left subtree swaps with the right subtree. The quintessential problem for mastering tree recursion and depth-first traversal.

1 approach(O(n))
Learn logic
EasyDynamic Programming
Visualizer

Climbing Stairs

Count the distinct ways to reach the top of an n-step staircase when hopping 1 or 2 steps at a time. The premier gentle introduction to Dynamic Programming and state transition.

1 approach(O(n))
Learn logic
EasyTrees & BST
Visualizer

Subtree of Another Tree

Determine if a binary tree contains a subtree identical in structure and node values to another tree. Learn how to combine outer tree DFS traversal with inner tree isomorphism matching.

1 approach(O(n * m))
Learn logic