0104.md

104. Maximum Depth of Binary Tree

Level:

Topic:

Question

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Input: root = [3,9,20,null,null,15,7]
Output: 3

Intuition

Recursive

• if root == null, it should return 0 (as well as add it to the current depth)
• every time to traverse the child node + 1 and compare the left and right subtree depth

Iterative

• use level order traversal, every level will +1 to the depth

Code

Time: O(log n) best case if it's balanced already
Space: O(n)

Recursive

public int maxDepth(TreeNode root) {
    if (root == null)
        return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

Iterative

public int maxDepth(TreeNode root) {
    int depth = 0;

    Queue<TreeNode> queue = new LinkedList<>();
    if (root != null)
        queue.add(root);

    while (!queue.isEmpty()) {

        int n = queue.size();
        while (n-- > 0) {
            root = queue.poll();
            if (root.left != null)
                queue.add(root.left);
            if (root.right != null)
                queue.add(root.right);
        }
        depth++;
    }
    return depth;
}