Reference: LeetCode
Difficulty: Easy

Problem

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7]:

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

The return depth should be 3.

Analysis

First, let’s be clear about the definition of height and depth of a tree or a node.

According to CS 61B, EPI p129, and a post on Stack Overflow:

  • The height of a node is the maximum number of edges / links to any leaf.
    • The height of a tree is the height of the root node.
  • The depth of a node is the number of edges / links to the root.
    • The maximum depth of a tree is equal to the height of the tree.

However, according to the problem description, the maximum depth in this problem equals to the maximum number of nodes to any leaf. In other words, it is one plus our formal definition of height / maximum depth of a tree.

Methods:

Whether the tree is balanced or not does not matter.

  1. Recursion
    • DFS (postorder) traverse the tree.
    • Time: $O(N)$ since we visit each node exactly once no matter the tree is balanced or not.
    • Space: $O(N)$ in the worst case; $O(\log{N})$ in the best case (balanced tree).
  2. Tail Recursion + BFS
    • The above recursion solution is probably not optimal in terms of space complexity. We can tweak the solution and make it tail recursion, so the compiler might optimize our code (reusing the same function call stack frame).
    • To make it tail recursion, we just need to make sure that the recursive call is the last action in the function.
    • Note: Optimization of tail recursion is not supported by Python or Java. And it is quite complicated.
    • Note: A function cannot be tail recursion if there are multiple occurrences of recursive calls in the function, even if the last action is the recursive call, e.g. return f(n - 1) + f(n - 1).
  3. Iteration
    • With the help of a stack, we can simulate the function call process.
    • Idea: Keep the next nodes to visit in a stack
    • Time: $O(N)$
    • Space: $O(N)$ in the worst case; $O(\log{N})$ in the best case (balanced tree).

Code

Test Case:

1
2
3
4
5
6
7
8
[3,9,20,null,null,15,7]
3
[]     // null
0
[1]    // 1 node
1
[1,2]  // 2 nodes
2

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int maxDepth(TreeNode root) {
  return depth(root);
}

// Formal
//  null     O      O    O
//                 /    / \
//                O    O   O
//   -1      0    1      1     <-- height (formal definition)
private int height(TreeNode x) {
  if (x == null) return -1;
  return Math.max(height(x.left), height(x.right)) + 1;
}

// This problem
//  null     O      O    O
//                 /    / \
//                O    O   O
//   0       1    2      2     <-- depth (according to the problem description)
private int depth(TreeNode x) {
  if (x == null) return 0;
  return Math.max(depth(x.left), depth(x.right)) + 1;
}

Iteration

Note:

  • The initial depth should be 1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int iteration(TreeNode root) {
  if (root == null) return 0;
  
  Stack<TreeNode> nodeStack = new Stack<>();
  Stack<Integer> dpStack = new Stack<>();
  
  nodeStack.push(root);
  dpStack.push(1);
  
  int currentDepth = 0;
  int maxDepth = Integer.MIN_VALUE;
  
  while (nodeStack.size() > 0) { // postorder
    TreeNode p = nodeStack.pop();
    currentDepth = dpStack.pop();
    if (p != null) {
      maxDepth = Math.max(maxDepth, currentDepth);
      nodeStack.add(p.left);
      nodeStack.add(p.right);
      dpStack.add(currentDepth + 1);
      dpStack.add(currentDepth + 1);
    }
  }
  return maxDepth;
}