CMD Guide
Home › DSA › Company Practice

easy Minimum Depth of a Binary Tree

Problem Statement

Given a root of the binary tree, find the minimum depth of a binary tree.

The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.

Examples

Example 1

Image
Image

Example 2

Image
Image

Constraints:

Try it yourself

Try solving this question here:

🎯 STRICT STANDOUT — Minimum Depth of a Binary Tree easy

0. Why / judgment (K3)

Family: BFS level order · first leaf depth

Min depth = shortest root→leaf path (#nodes). BFS guarantees first leaf found is minimum depth — better average than DFS when min leaf is shallow. DFS works but must explore all paths (or prune carefully).

1. Pattern + recognition + when-NOT (K12)

Pattern / template: Queue BFS with depth; when node has no left/right, return depth. Empty tree → 0. Recognition: shortest path in unweighted tree to a leaf.

When-NOT: Not max depth (DFS height). Critical mis-tag: minDepth is NOT 1+min(l,r) when a child is null — a null child is not a leaf path; only nodes with both children null are leaves. Classic bug: [1,2] min depth 2 not 1.

2. Complexity derivation (K11)

Time O(n) worst (visit all). Space O(w) width.
Best case O(min-depth level size) with BFS early exit.

3. Edge hand-run (K13)

null → 0.
single node → 1.
skewed left chain length k → k.
[1,2]: leaf is 2 at depth 2 (1 has right null but left exists — not leaf).

4. Interviewer follow-ups & drills

Q1. Why BFS preferred?
Model answer: Early exit at first leaf; optimal for small min depth.

Q2. DFS formula trap?
Model answer: Ignore null child when other exists — use +∞ for missing side.

Q3. Diameter vs min depth?
Model answer: Diameter longest path; different metric.

✅ Solution Minimum Depth of a Binary Tree

Problem Statement

Given a root of the binary tree, find the minimum depth of a binary tree.

The minimum depth is the number of nodes along the shortest path from the root node to the nearest leaf node.

Examples

Example 1

Image
Image

Example 2

Image
Image

Constraints:

  • The number of nodes in the tree is in the range [0, 105].
  • -1000 <= Node.val <= 1000

Solution

To solve this problem, we use a Breadth-First Search (BFS) approach to find the minimum depth of a binary tree. BFS is ideal for this problem because it explores nodes level by level, ensuring that we find the closest leaf node (node without children) to the root as quickly as possible.

Starting from the root, we traverse the tree level by level, and for each node, we check if it is a leaf node. The moment we encounter the first leaf node, we return the depth of that node as it represents the minimum depth of the tree. By using a queue to keep track of nodes at each level, we can efficiently manage this traversal.

Step-by-Step Algorithm

  1. Check if the tree is empty:

    • If the root is null, return 0 as the tree has no depth.

  2. Initialize the BFS queue:

    • Create an empty queue and add the root node to it.
    • Initialize a variable minimumTreeDepth to 0 to keep track of the depth as we traverse each level.

  3. Start BFS traversal:

    • While the queue is not empty, perform the following steps:
      • Increment the minimumTreeDepth by 1 to account for the current level.
      • Determine the number of nodes at the current level by checking the size of the queue.

  4. Process each node at the current level:

    • For each node in the current level, perform the following:
      • Dequeue the node from the queue.
      • Check if the node is a leaf node (both left and right children are null).
      • If it is a leaf node, return the current minimumTreeDepth as this is the minimum depth of the tree.

  5. Add children to the queue:

    • If the node is not a leaf, add its left and right children to the queue (if they exist) to be processed in the next level.

  6. Repeat until the queue is empty:

    • Continue processing each level until the queue is empty, which indicates that all nodes have been traversed. The first leaf node encountered will provide the minimum depth.

Algorithm Walkthrough

Image
Image

  1. Initialization:

    • Start with the root node 12.
    • Initialize an empty queue and add the root node 12 to it.
    • Set minimumTreeDepth to 0.

  2. Start BFS Traversal:

    • The queue contains [12].
    • Increment minimumTreeDepth to 1 because we are starting at the first level.

  3. Process the first level (root node 12):

    • The size of the queue is 1, indicating one node at this level.
    • Dequeue node 12 from the queue.
    • Check if node 12 is a leaf node (both left and right children are null):
      • Node 12 is not a leaf node, as it has left and right children.
    • Add the left child 7 and the right child 1 of node 12 to the queue.
    • The queue now contains [7, 1].

  4. Process the second level (nodes 7 and 1):

    • The queue contains [7, 1].

    • Increment minimumTreeDepth to 2 because we are moving to the second level.

    • The size of the queue is 2, indicating two nodes at this level.

    • Processing node 7:

      • Dequeue node 7 from the queue.
      • Check if node 7 is a leaf node:
        • Node 7 is a leaf node (no left or right children).
      • Since node 7 is a leaf node, return the current minimumTreeDepth, which is 2.

Final Output: The minimum depth of the tree [12, 7, 1, null, null, 10, 5] is 2.

Code

Here is the code for this algorithm:

java
import java.util.*;

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

//   TreeNode(int x) {
//     val = x;
//   }
// };

class Solution {

  public int findDepth(TreeNode root) {
    if (root == null) return 0;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int minimumTreeDepth = 0;
    while (!queue.isEmpty()) {
      minimumTreeDepth++;
      int levelSize = queue.size();
      for (int i = 0; i < levelSize; i++) {
        TreeNode currentNode = queue.poll();

        // check if this is a leaf node
        if (
          currentNode.left == null && currentNode.right == null
        ) return minimumTreeDepth;

        // insert the children of current node in the queue
        if (currentNode.left != null) queue.add(currentNode.left);
        if (currentNode.right != null) queue.add(currentNode.right);
      }
    }
    return minimumTreeDepth;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    TreeNode root = new TreeNode(12);
    root.left = new TreeNode(7);
    root.right = new TreeNode(1);
    root.right.left = new TreeNode(10);
    root.right.right = new TreeNode(5);
    System.out.println("Tree Minimum Depth: " + sol.findDepth(root));
    root.left.left = new TreeNode(9);
    root.right.left.left = new TreeNode(11);
    System.out.println("Tree Minimum Depth: " + sol.findDepth(root));
  }
}

Complexity Analysis

Time Complexity

The time complexity of the above algorithm is , where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.

Space Complexity

The space complexity of the above algorithm will be which is required for the queue. Since we can have a maximum of N/2 nodes at any level (this could happen only at the lowest level), therefore we will need space to store them in the queue.

Similar Problems

Problem 1: Given a binary tree, find its maximum depth (or height) using Tree BFS traversal.

Solution: We will follow a similar approach. Instead of returning as soon as we find a leaf node, we will keep traversing for all the levels, incrementing maximumDepth each time we complete a level. Here is what the code will look like:

Here is the visual representation of the algorithm:

Image
Image

Code

Here is the code for this algorithm:

java
import java.util.*;

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

//   TreeNode(int x) {
//     val = x;
//   }
// };

class Solution {
  public static int findDepth(TreeNode root) {
    if (root == null)
      return 0;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    int maximumTreeDepth = 0;
    while (!queue.isEmpty()) {
      maximumTreeDepth++;
      int levelSize = queue.size();
      for (int i = 0; i < levelSize; i++) {
        TreeNode currentNode = queue.poll();
        // insert the children of current node in the queue
        if (currentNode.left != null)
          queue.add(currentNode.left);
        if (currentNode.right != null)
          queue.add(currentNode.right);
      }
    }

    return maximumTreeDepth;
  }

  public static void main(String[] args) {
    TreeNode root = new TreeNode(12);
    root.left = new TreeNode(7);
    root.right = new TreeNode(1);
    root.right.left = new TreeNode(10);
    root.right.right = new TreeNode(5);
    System.out.println("Tree Maximum Depth: " + Solution.findDepth(root));
    root.left.left = new TreeNode(9);
    root.right.left.left = new TreeNode(11);
    System.out.println("Tree Maximum Depth: " + Solution.findDepth(root));
  }
}

Complexity Analysis

Time Complexity

The time complexity of the above algorithm is , where ‘N’ is the total number of nodes in the tree. This is due to the fact that we traverse each node once.

Space Complexity

The space complexity of the above algorithm will be which is required for the queue. Since we can have a maximum of N/2 nodes at any level (this could happen only at the lowest level), therefore we will need space to store them in the queue.

🎯 STRICT STANDOUT — Solution Minimum Depth of a Binary Tree

0. Why / judgment (K3)

Family: BFS first leaf

Solution must define leaf correctly: no children. BFS level counter or store depth in queue pairs. DFS alternative: if only one child, recurse that side only.

1. Pattern + recognition + when-NOT (K12)

Pattern / template: BFS queue; return depth at first leaf.

When-NOT: Don't copy max-depth code with min and forget null-child case.

2. Complexity derivation (K11)

O(n)/O(n).

3. Edge hand-run (K13)

Hand-run tree 1→(2,null): queue (1,d1); expand to (2,d2); 2 leaf → 2.
Complete small tree depth 2 leaves → 2.

4. Interviewer follow-ups & drills

Q1. Iterative DFS stack?
Model answer: Works; no early exit guarantee.

Q2. Morris?
Model answer: Overkill and awkward for depth-to-leaf.

Q3. Hostile 1e5 chain?
Model answer: BFS/DFS O(n); stack depth O(n) risk recursive.

🧩 Pattern · Trees

Recognize it: Hierarchical data → recurse on children; BFS (queue) for level-order, DFS (recursion) for paths.

▶ Visualize this problem (step it, predict each fork)
⛶ Open this problem debugger in explore mode
🤖 Don't fully get this? Learn it with Claude

Stuck on Minimum Depth of a Binary Tree? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Minimum Depth of a Binary Tree** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Minimum Depth of a Binary Tree** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Minimum Depth of a Binary Tree**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Minimum Depth of a Binary Tree**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Second Minimum Node In a Binary TrReverse a LinkedList →