Leetcode 104. Maximum Depth of Binary Tree

Maximum Depth of Binary Tree

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.

Recursive Approach 1:


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

Time Complexity: O(n) and Space Complexity: O(n)

Recursive(Explicit) Approach 2:


class Solution {
    public int maxDepth(TreeNode root) {
        LinkedList stack = new LinkedList<>();
        LinkedList depths = new LinkedList<>();
        if (root == null)
            return 0;

        stack.add(root);
        depths.add(1);

        int depth = 0, current_depth = 0;
        while (!stack.isEmpty()) {
            root = stack.pollLast();
            current_depth = depths.pollLast();
            if (root != null) {
                depth = Math.max(depth, current_depth);
                stack.add(root.left);
                stack.add(root.right);
                depths.add(current_depth + 1);
                depths.add(current_depth + 1);
            }
        }
        return depth;
    }
}

Time Complexity: O(n) and Space Complexity: O(n)

The "Maximum Depth of Binary Tree" problem involves finding the longest path from the root node to any leaf node in a binary tree. The maximum depth is defined as the number of nodes along the longest path from the root to the furthest leaf node.

The problem is important in tree-based algorithms as the depth of the tree affects the performance of tree operations, such as searching and balancing. A deeper tree might require more time to traverse, so finding the maximum depth can help optimize such operations.

Problem Statement

Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the furthest leaf node.

The tree is represented by the TreeNode class. You need to implement a function to compute the maximum depth of the tree.

Approach

To solve this problem, we can use a depth-first search (DFS) approach, where we recursively traverse the tree, calculating the depth of each subtree and returning the maximum depth of the tree. Another alternative is to use a breadth-first search (BFS), but DFS is simpler for this problem because we are only concerned with the depth of the tree.

The main idea behind the DFS approach is:

Traverse the tree from the root down to the leaf nodes.
At each node, calculate the depth of the left and right subtrees.
The maximum depth of the current node is the greater of the two depths (left and right), plus one.
Return the maximum depth of the entire tree.

This approach works efficiently by utilizing recursion to compute the depths of the subtrees, with the depth at each level of the tree being calculated recursively.

Algorithm

The algorithm for the maximum depth using DFS can be summarized as follows:

If the tree is empty (i.e., the root is null), return 0.
Recursively calculate the depth of the left subtree.
Recursively calculate the depth of the right subtree.
The maximum depth of the current node is the greater of the left and right subtree depths, plus one.
Return the maximum depth of the entire tree.

This approach ensures that the tree is traversed fully and the maximum depth is calculated by considering the deepest path from the root to a leaf node.

Example

Consider the following binary tree:

The maximum depth of this tree is 3, because the longest path from the root to a leaf node is from 1 -> 2 -> 4 or 1 -> 2 -> 5.

Now, consider a tree with just a single node:

The maximum depth in this case is 1, as there is only the root node, which is also a leaf.

Code Implementation

Below is the Python code to find the maximum depth of a binary tree using a DFS approach:

- The function `maxDepth` is a recursive function that calculates the maximum depth of the tree. - If the root is null (i.e., the tree is empty), it returns 0. - The left and right subtree depths are computed recursively. - The maximum of the two depths is returned, plus 1 to account for the current node.

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once to calculate the depth of the left and right subtrees.

The space complexity is O(h), where h is the height of the tree, due to the recursion stack. In the worst case, for a skewed tree (e.g., a linked list), the height will be O(n), so the space complexity will be O(n). For a balanced tree, the height will be O(log n), resulting in a space complexity of O(log n).

Optimized Approach

The current DFS approach is optimal in terms of time complexity since we only traverse each node once. The recursion depth is proportional to the height of the tree, so the space complexity is determined by the height of the tree.

If you need to reduce the recursion depth, an iterative approach using a breadth-first search (BFS) can be considered, but the time complexity will still be O(n).

Time Complexity (Optimized)

The time complexity remains O(n), where n is the number of nodes in the binary tree. The space complexity is O(h), where h is the height of the tree, due to the recursion stack. In the worst case, for an unbalanced tree, the height will be O(n), resulting in a space complexity of O(n). For a balanced tree, the height will be O(log n), so the space complexity will be O(log n).

Conclusion

The "Maximum Depth of Binary Tree" problem involves finding the longest path from the root to a leaf node. The DFS approach provides an efficient solution with a time complexity of O(n) and a space complexity of O(h), where n is the number of nodes and h is the height of the tree.