Maximum Depth of Binary Tree

Easy
1864.

Maximum Depth of Binary Tree

Maximum Depth of Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google, Microsoft and LinkedIn interviews.

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

Example 1

Input
root = [3,9,20,null,null,15,7]
Output
3
Explanation
The longest root-to-leaf paths are 3 → 20 → 15 and 3 → 20 → 7, each with three nodes.

Example 2

Input
root = [1,null,2]
Output
2

Example 3

Input
root = []
Output
0

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -100 <= Node.val <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Depth of Binary Tree — Problem & Solution

Maximum Depth of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Maximum Depth of Binary Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google, Microsoft and LinkedIn interviews.

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 the farthest leaf. An empty tree has depth 0.

Example 1

Input: root = [3,9,20,null,null,15,7]
Output: 3
Explanation: The longest root-to-leaf paths are 3 → 20 → 15 and 3 → 20 → 7, each with three nodes.

Example 2

Input: root = [1,null,2]
Output: 2

Example 3

Input: root = []
Output: 0

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -100 <= Node.val <= 100

Hints for Maximum Depth of Binary Tree

  1. Hint 1

    The depth of a tree is one more than the depth of its deeper subtree.

  2. Hint 2

    That gives a two-line recursion whose base case is the empty tree, with depth 0.

  3. Hint 3

    Without recursion: a breadth-first search counts how many levels it processes.

How to solve Maximum Depth of Binary Tree

Depth satisfies depth(node) = 1 + max(depth(node.left), depth(node.right)) with depth(null) = 0, so one post-order recursion computes it.

Approach

  1. If root is null, return 0.
  2. Compute the depths of the left and right subtrees recursively.
  3. Return 1 + max(left, right).

Why it works

Any root-to-leaf path leaves the root through exactly one child, so the longest one is the root plus the longest path in whichever subtree is deeper — exactly what the recurrence takes.

Complexity

  • Time — O(n)
  • Space — O(h) recursion depth; a level-by-level BFS uses O(width) instead

Pitfalls

  • Depth counts nodes, not edges: a single node has depth 1.
  • An empty tree has depth 0.

Reference solution

Python

from typing import Optional

def maxDepth(root: Optional[TreeNode]) -> int:
    if root is None:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

Java

public static int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

C++

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}

JavaScript

var maxDepth = function(root) {
    if (root === null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)