DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Maximum Depth of Binary Tree

easyTrees Must-do

Problem statement

Given the root of a binary tree, return its maximum depth: the number of nodes on the longest path from the root down to any leaf. An empty tree has depth 0, and a tree with only a root has depth 1.

Trees in the examples are written in level order, left to right, with null for a missing child.

Examples

Example 1

Input: root = [5, 3, 8, null, null, 6, 9, null, 7]

Output: 4

Explanation: The longest path is 5 -> 8 -> 6 -> 7.

Example 2

Input: root = [1, null, 2]

Output: 2

Hints

Approach

The definition is already recursive: a tree's depth is one more than the depth of its deeper child subtree.

  1. If root is empty, return 0.
  2. Otherwise return 1 + max(maxDepth(root.left), maxDepth(root.right)).

Each node is visited once. The recursion stack is as deep as the tree is tall, which is O(log n) for a balanced tree and O(n) for a tree that is really a chain.

ComplexityTime O(n)Space O(h), where h is the height of the tree
Python
from typing import Optional
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def maxDepth(self, root: Optional["TreeNode"]) -> int:
if root is None:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

Follow-up questions

  • Return the minimum depth instead: the number of nodes on the shortest path to a leaf.
  • Given a list of file paths, return the depth of the deepest directory.

Frequently asked questions

Here it counts nodes, so a single root has depth 1. Some textbooks define height in edges, which would make that 0. Read the problem and the example for the empty tree to be sure.

For a very deep chain, yes. Python's default recursion limit is about 1,000 frames. The BFS version, or an iterative DFS with an explicit stack of (node, depth) pairs, avoids that.

Directory trees, process trees, DNS zones and nested configuration are all trees. Finding the deepest path is the same as finding the most deeply nested directory or the longest chain of child processes.