Finding Minimum Depth of Binary Tree in C++

In this article, we will learn how to find the minimum depth of a binary tree in C++ with the help of the code example.

The minimum distance between the root node and the left node in a binary tree is called its minimum depth.

Below is a given given example:

Input:
         7
        / \
       3   5
      / \
     1   2
Output: The minimum depth of the given binary tree: 2
Exaplanation: 7 -> 5

Minimum Depth of Binary Tree in C++

We are going to solve this problem using a recursive approach.

1. At the very first, create a tree using struct.

2. After that, create a function minDepth and pass the root node as an argument.

• Now check the base case where the tree has no element i.e. root == NULL.
• Check whether the tree has only one element if true return 1.
• Now transverse through the right subtree and left subtree.

3. Finally, return the minimum depth between the right subtree and left subtree.

Below is the complete code:

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    struct Node *left;
    struct Node *right;
};
int minDepth(Node *root){
    if (root == NULL)
        return 0;
    
    if(root->left == NULL && root->right == NULL)
        return 1;
    
    if (!root->left)
    return minDepth(root->right)+1;

    if(!root->right)
    return minDepth(root->left)+1;

    return min(minDepth(root->left), minDepth(root->right))+1;
}
void inorder(Node* root){
    if (root == NULL)
    return;

    inorder(root->left);
    cout<<root->data<<" ";
    inorder(root->right);
}
Node *newNode(int data){
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
int main(){
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->right = newNode(4);
    root->left->left = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(8);
    root->left->left->left = newNode(7);
    cout<<"The inorder of given binary tree: ";
    inorder(root);
    cout<<endl;
    cout<<"The minimum depth of the given binary tree is "<<minDepth(root);
    return 0;
}

Output

The inorder of given binary tree: 7 5 2 4 1 6 3 8 
The minimum depth of the given binary tree is 3

Exaplanation: 1 -> 2 -> 4 is one of the minimum depth.

Also, read

• Check whether a binary tree is a full binary tree in C++
• Height of a binary tree in C++