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.

Minimum Depth is 3

The minimum depth of the binary tree is 3. Now there are total three paths where we have a total of 3 nodes from root to leaf.

6 -> 2 -> 0
6 -> 8 -> 7
6 -> 8 -> 9

A small recursive DFS solution is good to find the answer.

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

The drawback of the DFS approach in this case is that all nodes should be visited to ensure that the minimum depth would be found. Therefore, this results in a O(N) complexity. One way to optimize the complexity is to use the BFS strategy. We iterate the tree level by level, and the first leaf we reach corresponds to the minimum depth. As a result, we do not need to iterate all nodes.

class Solution {
    public int minDepth(TreeNode root) {
        
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 1;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0 ; i < size ; i++){
                TreeNode curNode = queue.poll();
                if(isLeaf(curNode)){
                    return depth;
                }
                if(curNode.left != null){
                    queue.offer(curNode.left);
                }
                if(curNode.right != null){
                    queue.offer(curNode.right);
                }
            }
            depth++;
        }
        return 0;
    }
    
    private boolean isLeaf(TreeNode node){
        return node != null && node.left == null && node.right == null;
    }
}

Complexity analysis

  • Time Complexity : O(N).
  • Space Complexity : O(N).

In the worst case of the BFS method, we have a tree like this:

   1
    \
     2
      \
       3
        \
         4

And in this case, we need to visit every node until we get to the only leaf node. So we need to visit N nodes in the worst case.

Categories: Binary Tree

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s