Leetcode 111. Minimum Depth of Binary Tree

Minimum Depth of Binary Tree

Leetcode 111. Minimum Depth of Binary Tree : Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. Note: A leaf is a node with no children.

DFS Recursive Method Approach 1:


class Solution {
    public int minDepth(TreeNode root) {
        return dfs(root);
    }
    
    //DFS Recursive Method
    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }

        // If only one of child is non-null, then go into that recursion.
        if (root.left == null) {
            return 1 + dfs(root.right);
        } else if (root.right == null) {
            return 1 + dfs(root.left);
        }

        // Both children are non-null, hence call for both childs.
        return 1 + Math.min(dfs(root.left), dfs(root.right));
    }
}

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

Recursive concise Approach 2:


    class Solution {

        public int minDepth(TreeNode root) {
            if (root == null)
                return 0;
            int h1 = this.minDepth(root.left);
            int h2 = this.minDepth(root.right);
            return h1 == 0 || h2 == 0 ? 1 + Math.max(h1, h2) : 1 + Math.min(h1, h2);
        }
    }

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

iterative & recursive:


    class Solution {
        //iterative
        public int minDepth(TreeNode root) {
            if (root == null)
                return 0;
            Queue q = new LinkedList<>();
            int lvl = 0;
    
            q.offer(root);
            while (!q.isEmpty()) {
                lvl++;
                int curr = q.size();
                for (int i = 0; i < curr; i++) {
                    TreeNode temp = q.poll();
                    if (temp.left == null && temp.right == null)
                        return lvl;
                    if (temp.left != null)
                        q.offer(temp.left);
                    if (temp.right != null)
                        q.offer(temp.right);
                }
            }
            return 0;
        }
    
        // recursive
        public int minDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = minDepth(root.left);
            int right = minDepth(root.right);
            if (left == 0 || right == 0) {
                if (left != 0 || right != 0) {
                    return Math.max(left, right) + 1;
                } else {
                    return 1;
                }
            } else {
                return Math.min(left, right) + 1;
            }
        }
    }

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

The "Minimum Depth of Binary Tree" problem involves finding the shortest path from the root to a leaf node in a binary tree. In this case, the minimum depth is defined as the number of nodes along the shortest path from the root node to the nearest leaf node.

A leaf node is a node that has no children. This problem is useful in various scenarios like finding the shortest path or minimizing the number of steps needed to reach a destination in a tree structure.

Problem Statement

Given a binary tree, return its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

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

Approach

To solve the problem, we can use either a breadth-first search (BFS) or a depth-first search (DFS) approach. Both approaches work, but BFS is preferred for this problem because it ensures that we find the minimum depth in the shortest time by exploring level by level.

The idea behind the BFS approach is:

Start from the root node.
Explore the nodes level by level using a queue, and check if a node is a leaf (has no children).
If a leaf node is found, return the current depth.
If no leaf node is found in the current level, continue to the next level.

The DFS approach, on the other hand, involves recursively traversing the tree and returning the minimum depth of the left and right subtrees. It works well but may not be as efficient as BFS in this case.

Algorithm

The algorithm for the minimum depth using BFS can be summarized as follows:

If the tree is empty (root is null), return 0.
Create a queue to store nodes along with their depth.
Start by adding the root node with depth 1 to the queue.
While the queue is not empty, dequeue the front node and check if it is a leaf node.
If the node is a leaf, return its depth (this is the minimum depth).
If the node is not a leaf, enqueue its left and right children with depth incremented by 1.
If all nodes are explored, return the depth of the first leaf node encountered.

This approach guarantees that we find the minimum depth because BFS explores all nodes at a given depth level before moving to the next level.

Example

Consider the following binary tree:

The minimum depth of this tree is 2, because the shortest path to a leaf node is from the root (1) to node 3 (a leaf node).

Now, consider a tree where the root has only one child:

In this case, the minimum depth is 3, as the only path to a leaf node is from the root to node 2 and finally to node 3.

- We use a queue to implement the BFS approach. - The queue stores tuples, where each tuple consists of a node and its current depth. - If a leaf node is found, the current depth is returned as the minimum depth. - If the node has children, they are added to the queue with an incremented depth.

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 in a breadth-first manner.

The space complexity is O(n) as well, due to the queue storing nodes at each level. In the worst case, when the tree is a complete binary tree, the queue may contain up to n/2 nodes at the last level, resulting in a space complexity of O(n).

Optimized Approach

The current approach is already optimal in terms of time complexity, as we traverse each node only once. However, if we were to use a DFS approach, the time complexity would still be O(n), but the space complexity might be reduced to O(h), where h is the height of the tree, as the DFS approach uses recursion.

In practice, BFS is preferred for this problem since it guarantees the shortest path to a leaf node while minimizing the depth exploration at each level.

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(n) due to the queue used in the BFS approach. If DFS is used, the space complexity would be O(h), where h is the height of the tree, as the recursion stack would be used.

Conclusion

The "Minimum Depth of Binary Tree" problem involves finding the shortest path from the root to a leaf node in a binary tree. The BFS approach is effective for this problem, ensuring the shortest path is found in the least number of steps. The time complexity of the solution is O(n), and the space complexity is O(n), where n is the number of nodes in the tree.