Max Depth of Binary Tree

Maximum Depth of Binary Tree (LC.104)

Given a binary tree, find its maximum depth.

Example

+    1
   /   \
  2     3
 / \
4   5
Max depth: 3

Analysis

If you can do D&C, always try D&C first. Traverse is longer to write.

Code

public int maxDepth(TreeNode root) {
    // base case
    if (root == null)
        return 0;

    // divide
    int leftSubtree = maxDepth(root.left);
    int rightSubtree = maxDepth(root.right);

    // conquer
    return 1 + Math.max(leftSubtree, rightSubtree);
}

Minimum Depth of Binary Tree (LC.111)

Given a binary tree, find its minimum depth.

Example

+    1
   /   \
  2     3
 /     /
4     5
Min depth: 3 (not 2)

Analysis

Divide and conquer again. But this time need to handle a special case where a subtree has a left child but no right child. Math.min(leftSubtree, rightSubtree) will give 0 but in truth we have 1.

Code

public int minDepth(TreeNode root) {
    // base case
    if (root == null)
        return 0;

    // divide
    int leftSubtree = minDepth(root.left);
    int rightSubtree = minDepth(root.right);

    // conquer
    if (Math.min(leftSubtree, rightSubtree) > 0) {
        return 1 + Math.min(leftSubtree, rightSubtree);
    } else {
        return 1 + Math.max(leftSubtree, rightSubtree);
    }
    // return 1 + (Math.min(L, R) > 0 ? Math.min(L, R) : Math.max(L, R));
}