# Finding the minimum depth of a binary tree The minimum depth of a binary tree is the depth or level of the topmost leaf node.
Example :

• In Tree A the first leaf node ( Node 20 ) is at level 2.
• In Tree B the first leaf node ( Node 6 ) is at level 6.

The trick to find the topmost leaf node is to use a level-order traversal. While doing a level order traversal, in each level we check if any of the nodes is a leaf node. The depth of the first found leaf node is the minimum depth of the tree.

Data structure used : Queue

Time Complexity : O ( n ), where n is the number of nodes in the tree. As the push O ( 1 ) and pop O ( 1 ) operations happen only once for every node in the tree the time complexity is O ( n ).

C++ program to find the minimum depth of a binary tree.

``````#include<iostream>
#include<queue>

using namespace std;

class Node {
public:
int data;
Node *left;
Node *right;
Node() : data(0), left(nullptr), right(nullptr) {}
Node(int x) : data(x), left(nullptr), right(nullptr) {}
Node(int x, Node *left, Node *right) : data(x), left(left), right(right) {}
};

int MinDepth (Node* root) {

int level = 0;

if (root == NULL)
return level;

queue<Node *> parent_queue, child_queue;

parent_queue.push(root);
level++;

while (!parent_queue.empty() or !child_queue.empty()) {

while (!parent_queue.empty()) {

Node * node = parent_queue.front();
parent_queue.pop();

// Check if a leaf node is reached. If so return the height.
if (node->left == nullptr and node->right == nullptr)
return level;
if (node->left != NULL)
child_queue.push(node->left);
if (node->right != NULL)
child_queue.push(node->right);
}

level++;

while (!child_queue.empty()) {

Node * node = child_queue.front();
child_queue.pop();
// Check if a leaf node is reached. If so return the height.
if (node->left == nullptr and node->right == nullptr)
return level;
if (node->left != NULL)
parent_queue.push(node->left);
if (node->right != NULL)
parent_queue.push(node->right);
}

level++;
}
return level;
}

int main () {

/* Minimum height 6
1
\
2
\
3
\
4
\
5
\
6 */
Node n6 (6, nullptr, nullptr);
Node n5 (5, nullptr, &n6);
Node n4 (4, nullptr, &n5);
Node n3 (3, nullptr, &n4);
Node n2 (2, nullptr, &n3);
Node n1 (1, nullptr, &n2);

cout << "Minimum depth of the tree with node (" << n1.data << ") : "  << MinDepth(&n1) << endl;

/* Minimum height 2
10
/  \
20  30
/  \
40   50 */

Node n50 (50, nullptr, nullptr);
Node n40 (40, nullptr, nullptr);
Node n30 (30, &n40, &n50);
Node n20 (20, nullptr, nullptr);
Node n10 (10, &n20, &n30);

cout << "Minimum depth of the tree with node (" << n10.data << ") : "  << MinDepth(&n10) << endl;
return 0;
}
``````

Output

``````Minimum depth of the tree with node (1) : 6
Minimum depth of the tree with node (10) : 2
``````