On this page

Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth: the number of nodes along the longest path from the root down to a leaf.

Constraints:

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

Intuition

1 1
2 / \
3 2 3
4 / \ \
5 4 5 6

The depth of this tree is 3. Think of it recursively: the depth of a tree is one (for the root) plus the deeper of its two subtrees. An empty tree has depth 0, which is the base case.

This is a postorder idea: you need the answers from both children before you can answer for the parent.

Approach: Recursion

  1. If the node is null, return 0.
  2. Ask the left subtree for its depth, lh.
  3. Ask the right subtree for its depth, rh.
  4. Return 1 + max(lh, rh).

A level-order (BFS) traversal also works: count how many levels the queue goes through. The recursive version is shorter and is the building block for the next few problems (balanced tree, diameter, max path sum).

Code

class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
int lh = maxDepth(root->left);
int rh = maxDepth(root->right);
return 1 + max(lh, rh);
}
};

Complexity

Time: O(n)

Every node is visited exactly once.

Space: O(h)

The recursion stack goes as deep as the tree height: O(log n) when balanced, O(n) when skewed.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"The depth of a tree is one plus the larger depth of its two subtrees, and an empty tree has depth zero. So I recurse: if the node is null I return zero, otherwise I get the left depth and the right depth and return one plus the max of the two. Every node is visited once, so time is O of n, and the recursion stack is as deep as the tree is tall, so space is O of h. A level order traversal counting levels also works, but this recursive pattern is the one I reuse for balanced tree, diameter and max path sum."
Next TopicBalanced Binary Tree