3.1 Max Depth of Binary Tree

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.

Logical Steps

1. Empty root have 0 depth, return 0 as base case
2. Divide: recursively calculate maxDepth of left tree and right tree
3. Conquer: pick maxDepth from left and right, and +1 on top of it for current level

Code Template

public int maxDepth(TreeNode root) {
    // base case:
    // if root is null, empty tree has no level, return 0
    if (root == null)
        return 0;

    // divide
    // recursively calculate left and right maxDepth
    int left = maxDepth(root.left);
    int right = maxDepth(root.right);

    // conquer
    // pick max depth from left and right, and +1 on top of it
    return Math.math(left, right)+1;
}

Common Mistakes

1. Assign +1 to maxDepth before divide: since maxDepth has to take value from left and right and pick max, its just not gonna do anything.

2. Forget to add Math.math(left, right) by 1: current level maxDepth will not be calculated, maxDepth will always be 0.

    public int maxDepth(TreeNode root) {
        // base case:
        // for empty root, the depth of level is 0
        if (root == null){
            return 0;
        }
   
        // misplaces +1 here
        maxDepth = maxDepth + 1;
   
        //divide
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
   
        // missing + 1 here
        int maxDepth = Math.max(left, right);
   
        return maxDepth;
    }