Maximum Depth of Binary Tree

The problem

A binary tree is made of nodes. Each node has a value, val, and two children, left and right; a missing child is null. A node with no children is called a leaf. You are given root, the top node, or null for an empty tree. The depth of the tree is the number of nodes on the longest path that starts at the root and goes down, from parent to child, to a leaf. Return the depth. An empty tree has depth 0.

What to write

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };

function solve(root: TreeNode | null): number

Input
root = {"val":1,"left":{"val":2,"left":null,"right":null},"right":null}

Output
2

Input
root = null

Output
0

Constraints

0–500 acyclic tree nodes; integer values.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The tree may be empty, and then the answer is 0. The deepest leaf can sit at the end of any branch, so no node can be skipped. With at most 500 nodes, visiting every one of them is cheap.

2. Hint 2: Ask a smaller question

   Start from example 1, where node 1 has the single child 2. Give node 2 a child of its own: what is the depth now? Go back and give node 1 a second child instead: what is the depth then? Why did only one of the two changes matter?

3. Hint 3: Name the pattern

   A child together with everything below it is a subtree, a smaller tree. A tree's depth depends only on the depths of its two subtrees, so the function can call itself on both children: that is recursion. The function's promise: given any node, return the depth of the tree that starts there. Children answer before their parent: postorder tree recursion. Read the lesson on postorder tree recursion.

4. Hint 4: State the invariant

   Every call returns the exact depth of the subtree it was given: 0 for a missing node, otherwise 1 for the node itself plus the larger of its two children's depths.

5. Hint 5: Sketch the pseudocode

   If the node is null, return 0. Otherwise call the function on the left child and on the right child to get two depths. Return 1 plus the larger of the two.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

An empty subtree has depth zero. Compute both child depths and add one to the larger result.

The slow way

Follow every path from the root down to a leaf, count the nodes on each one, and keep the largest count. This gives the right answer, but the same nodes are counted again and again: the root lies on every path, so the root alone is counted once for each leaf.

The insight

You never need the paths themselves. The longest way down from a node is the node itself followed by the longest way down from one of its children. So a node needs one number from each child: the depth of the child's subtree, which is the child together with everything below that child.

Step by step

1. An empty tree has depth 0. A missing child holds no nodes, so it adds no levels. Returning 0 here is also what stops the calls: every way down the tree ends at a missing child.
2. Find the depth of the left subtree and of the right subtree. The function calls itself, which is called recursion. It promises one thing: given any node, it returns the depth of the tree that starts there. Both sides are asked, because the deepest leaf may be on either.
3. This node adds one level on top of the deeper subtree. The longest path from this node starts with the node itself, which counts as 1, and continues along the longest path of whichever subtree is deeper.

The same numbered steps are the comments in each solution.

function solve(root) {
  // 1. An empty tree has depth 0
  if (!root) return 0;
  // 2. Find the depth of the left subtree and of the right subtree
  const left = solve(root.left);
  const right = solve(root.right);
  // 3. This node adds one level on top of the deeper subtree
  return 1 + Math.max(left, right);
}

type TreeNode = {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
};
function solve(root: TreeNode | null): number {
  // 1. An empty tree has depth 0
  if (!root) return 0;
  // 2. Find the depth of the left subtree and of the right subtree
  const left = solve(root.left);
  const right = solve(root.right);
  // 3. This node adds one level on top of the deeper subtree
  return 1 + Math.max(left, right);
}

def solve(root):
    # 1. An empty tree has depth 0
    if root is None:
        return 0
    # 2. Find the depth of the left subtree and of the right subtree
    left = solve(root.left)
    right = solve(root.right)
    # 3. This node adds one level on top of the deeper subtree
    return 1 + max(left, right)

Example 1, traced

Input
root = {"val":1,"left":{"val":2,"left":null,"right":null},"right":null}

Output
2

Why it works

For a missing node the function returns 0, which is right. For any other node, if the two calls on its children return the right depths, then 1 plus the larger of them is the number of nodes on the longest path down from that node. So every call is right, children first and then their parent, which is what postorder means.

Time and space

Time O(n), extra space O(h) call stack. The function runs once per node and once per missing child, with constant work each time: O(n) time. The unfinished calls form a chain from the root down, one per level: O(h) on the call stack, where h is the depth of the tree.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Return 0 for a missing node, not 1. With 1, every answer comes out one too large: example 1 would give 3 instead of 2, and an empty tree would have depth 1.
• Do not forget to add 1 for the node itself. Without that 1, the function returns the larger of two zeros at every node, so the answer is 0 for every tree.
• Take the larger of the two depths, not their sum. The sum counts every node in the tree: a tree of 8 nodes whose depth is 6 would give 8.

Pattern

Postorder tree recursion. Builds on Invert Binary Tree.

Keep going