Maximum Depth of Binary Tree

NeetCode: Maximum Depth of Binary Tree · LeetCode: 104. Maximum Depth of Binary Tree · Difficulty: Easy

Return the maximum depth of a binary tree: the number of nodes along the longest path from the root down to a leaf.

Example

Text

Input:  [1, 2, 3, null, null, 4]    Output: 3    (1 -> 3 -> 4)
Input:  []                          Output: 0

Both solutions visit each node once and run in O(n); the recursive version is shorter.

Trees are given in LeetCode's level-order array form: the root first, then each level from left to right, with null marking a missing node, so [1, 2, 3, 4, 5] is the tree above. The tree(Integer... values) helper in each program builds a TreeNode from such an array by filling children from a queue. TreeNode has the fields val, left, and right. A missing child is null: Java object references are nullable and the fields are mutable, so no wrapper type is needed.

Brute force: count levels with BFS

Process the tree one level at a time with a queue (ArrayDeque). The number of levels is the depth. The inner loop runs queue.size() times, which is read once before the loop starts, so it covers exactly the nodes of the current level.

Java

import java.util.ArrayDeque;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int depth = 0;
        while (!queue.isEmpty()) {
            depth++;
            for (int count = queue.size(); count > 0; count--) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
            }
        }
        return depth;
    }
}

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().maxDepth(tree(1, 2, 3, null, null, 4)));
        System.out.println(new Solution().maxDepth(tree()));
    }
}

Output

3
0

ArrayDeque rejects null, so only real nodes are added. Time: O(n). Space: O(w) for the widest level, up to O(n).

Optimal: recursive DFS

The depth of a tree is one (the root) plus the deeper of its two subtrees. An empty tree has depth 0.

Java

import java.util.ArrayDeque;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

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

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().maxDepth(tree(1, 2, 3, null, null, 4)));
        System.out.println(new Solution().maxDepth(tree()));
        System.out.println(new Solution().maxDepth(tree(7)));
    }
}

Output

3
0
1

Time: O(n). Space: O(h) for the recursion stack. A chain of many thousands of nodes can overflow the thread stack; the BFS version has no such limit.