Algotree > Algorithms > Tree & Graph Traversal > Finding the minimum depth of a binary tree

Finding the minimum depth of a binary tree

Minimum_Depth_Bin_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