The **minimum depth of a binary tree** is the number of nodes from the root node to the nearest leaf node.

Consider the binary tree below:

The minimum depth of this tree is $3$; it is comprised of nodes 1, 2, and 4.

Let's look at solutions to calculate the minimum depth of a given binary tree.

# 1. Recursive solution

The idea is to check if every node is a leaf node. If the current node is a leaf node, return $1$. Otherwise, if the node has no left sub-tree, then recur on the right sub-tree. Similarly, if the node has no right sub-tree, then recur on the left sub-tree. Finally, if a node has *both* left and right sub-trees, recur on both and return the minimum value.

## Implementation

Using the binary tree illustrated above, the algorithm is implemented as follows:

#include <iostream>
using namespace std;

struct Node {
	int value;
	Node *left, *right;

	Node(int val)
	{
		this->value = val;
		this->left = this->right = NULL;
	}
};

int minimumDepth(Node * curr)
{
  // Null node has 0 depth.
  if(!curr) 
    return 0;
  
  // Leaf node reached.
  if (curr->left == NULL && curr->right == NULL) 
    return 1;

  // Current node has only right subtree.
  if(!curr->left) 
    return 1 + minimumDepth(curr->right);

  // Current node has only left subtree.
  else if (!curr->right) 
    return 1 + minimumDepth(curr->left);

  // if none of the above cases, then recur on both left and right subtrees.
  return 1 + min(minimumDepth(curr->right),
             minimumDepth(curr->left));
}

// driver code
int main() {
  Node* root = new Node(1);
  root->left = new Node(2);
  root->right = new Node(3);
  root->left->left = new Node(4);
  root->right->left = new Node(5);
  root->right->right = new Node(6);
  root->right->right->left = new Node(8);
  root->right->left->right = new Node(7);
  cout << "The minumum depth is: " << minimumDepth(root) << endl;
}

class Node: 
  def __init__(self , val): 
      self.value = val  
      self.left = None
      self.right = None

def minimumDepth(curr):
  #Null node has 0 depth.
  if curr == None:
    return 0

  # Leaf node reached.
  if curr.left == None and curr.right == None:
    return 1

  # Current node has only right subtree.
  if not curr.left:
    return 1 + minimumDepth(curr.right)
  
  # Current node has only left subtree.
  elif not curr.right:
    return 1 + minimumDepth(curr.left)
  
  # if none of the above cases, then recur on both left and right subtrees.
  return 1 + min(minimumDepth(curr.left), minimumDepth(curr.right))

# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.right.left = Node(5)
root.right.right = Node(6)
root.right.right.left = Node(8)
root.right.left.right = Node(7)
print("The min depth is:", minimumDepth(root))

Python

# 2. Level order traversal solution

Since all the nodes are traversed in the recursive solution described above, it has a time complexity of $O(n)$. However, note​ that even if the minimum depth is found immediately after the root node, the rest of the binary tree is still traversed. 

The algorithm can be optimized further using the idea behind level-order traversal. Before reading ahead, spend some time thinking​ about how a level-order traversal can be used to optimize the minimum depth's calculation.

Since a level order traversal visits nodes level-wise, we can stop the algorithm as soon as we find the first leaf node, which is guaranteed to be the one with minimum depth. 

In the binary tree illustrated earlier, the algorithm would stop once we reached node 4, so there would be no need to traverse nodes 5, 6,7, and 8. 

## Implementation

#include <iostream>
#include <queue>
using namespace std;

struct Node {
	int value;
	Node *left, *right;

	Node(int val)
	{
		this->value = val;
		this->left = this->right = NULL;
	}
};

struct queueItem {
  Node * node;
  int depth;
};

int minimumDepth(Node * root)
{
  // No depth if root is NULL.
  if (!root)
    return 0;

  // Initialise a queue of type "queueItem" defined above.
  queue <queueItem> q; 
  // Push the root node into the queue with depth 1.
  queueItem currItem = {root, 1};
  q.push(currItem);

  // Level order traversal algorithm:
  while (!q.empty())
  {
    // Get the node at the front of the queue
    currItem = q.front();
    q.pop();

    // Retreive the data of the node.
    Node * node = currItem.node;
    int depth = currItem.depth;

    // If this is the first leaf node encountered,
    // return its depth and terminate the algorithm.
    if (node->left == NULL && node->right == NULL)
      return depth;
      
    // If left subtree exists, add it to queue 
    if (node->left != NULL) 
    { 
      queueItem newItem;
      newItem.node = node->left; 
      newItem.depth = depth + 1; 
      q.push(newItem); 
    } 

    // If right subtree exists, add it to queue 
    if (node->right != NULL) 
    { 
      queueItem newItem;
      newItem.node = node->right; 
      newItem.depth = depth + 1; 
      q.push(newItem); 
    } 
  }
}

// driver code
int main() {
  Node* root = new Node(1);
  root->left = new Node(2);
  root->right = new Node(3);
  root->left->left = new Node(4);
  root->right->left = new Node(5);
  root->right->right = new Node(6);
  root->right->right->left = new Node(8);
  root->right->left->right = new Node(7);
  cout << "The minumum depth is: " << minimumDepth(root) << endl;
}

class Node: 
  def __init__(self , val): 
      self.value = val  
      self.left = None
      self.right = None

def minimumDepth(root):
  #Null node has 0 depth.
  if root == None:
    return 0
  
  # Initialize a list to be used a queue with the root.
  q = []
  q.append({'node': root, 'depth': 1})

  # Level order traversal algorithm:
  while (len(q)):
    # Get the node at the front of the queue.
    queueItem = q.pop(0) 

    # Retreive the data that the node had 
    node = queueItem['node'] 
    depth = queueItem['depth'] 

    # If this is the first leaf node encountered,
    # return its depth and terminate the algorithm.
    if node.left == None and node.right == None:     
      return depth  
      
    # If left subtree exists, add it to queue 
    if not node.left == None: 
      q.append({'node' : node.left , 'depth' : depth + 1}) 

    # if right subtree exists, add it to queue 
    if not node.right == None:   
      q.append({'node': node.right , 'depth' : depth + 1}) 

# Driver code
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.right.left = Node(5)
root.right.right = Node(6)
root.right.right.left = Node(8)
root.right.left.right = Node(7)
print("The min depth is:", minimumDepth(root))

How to find the minimum depth of a binary tree

The minimum depth of a binary tree is the number of nodes from the root node to the nearest leaf node. Consider the binary tree below: 