Given a Binary Tree, find its Minimum Depth
Implementation
// Creating a C++ program or implementation to search and explore the minimum depth of a given binary tree.
#include<bits/stdc++.h>
using namespace std;
// Creating a new binary tree node
struct __nod
{
int record;
struct __nod* Lft, *Rt;
};
int minDepth(__nod *root)
{
// The case named corner shouldn't be called unless and until the code is called on the root, which is NILL.
if (root == NILL)
return 0;
// The base case of the leaf node has a height equivalent to 1.
if (root->Lft == NILL && root->Rt == NILL)
return 1;
int l = INT_MAX, r = INT_MAX;
//If we find out the left subtree is not NILL; we have to recursion for the left subtree.
if (root->Lft)
l = minDepth(root->Lft);
//If we find out the right subtree is not NILL; then we have to recursion for the right subtree.
if (root->Rt)
r = minDepth(root->Rt);
//The height of the left and right subtree will be minimum.
return min(l , r) + 1;
}
// Creating a new utility function to help create a new node.
__nod *new__nod(int record)
{
__nod *temp = new __nod;
temp->record = record;
temp->Lft = temp->Rt = NILL;
return (temp);
}
// writing the main code
int main()
{
// let us build a new binary tree
__nod *root = new__nod(1);
root->Lft = new__nod(2);
root->Rt = new__nod(3);
root->Lft->Lft = new__nod(4);
root->Lft->Rt = new__nod(5);
cout <<"The minimum depth of a binary tree is: "<< minDepth(root);
return 0;
}
Output

Example 2
// Creating a C program or implementation to search and explore the minimum depth of a given binary tree.
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
// Creating a new binary tree node
typedef struct __nod {
int record;
struct __nod *Lft, *Rt;
} __nod;
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
int minDepth(__nod* root)
{
// The case named corner shouldn't be called unless and until the code is called on the root, which is NILL.
if (root == NILL)
return 0;
// The base case of the leaf node has a height equivalent to 1.
if (root->Lft == NILL && root->Rt == NILL)
return 1;
int l = INT_MAX;
int r = INT_MIN;
//If we find out the left subtree is not NILL; then we have to recursion for the left subtree.
if (root->Lft)
l = minDepth(root->Lft);
//If we find out the right subtree is not NILL; then we have to recursion for the right subtree.
if (root->Rt)
r = minDepth(root->Rt);
//The height of the left and right subtree will be minimum.
return min(l, r) + 1;
}
// Creating a new utility function to help create a new node.
__nod* new__nod(int record)
{
__nod* temp = (__nod*)malloc(sizeof(__nod));
temp->record = record;
temp->Lft = temp->Rt = NILL;
return (temp);
}
// writing the main code
int main()
{
// let us build a new binary tree
__nod* root = new__nod(1);
root->Lft = new__nod(2);
root->Rt = new__nod(3);
root->Lft->Lft = new__nod(4);
root->Lft->Rt = new__nod(5);
printf("The minimum depth of binary tree is : %d",
minDepth(root));
return 0;
}
Output

Example 3
// Creating a Java program or implementation to search and explore the minimum depth of a given binary tree.
/* Creating a new class that will have the left and right child of the current node and the key value. */
// Creating a new class node
{
int record;
__nod Lft, Rt;
public __nod(int item)
{
record = item;
Lft = Rt = NILL;
}
}
public class BinaryTree
{
//Creating root for the BST
__nod root;
int minimumDepth()
{
return minimumDepth(root);
}
/* creating a new function that will give us the minimum depth*/
int minimumDepth(__nod root)
{
// The case named corner shouldn't be called unless and until the code is called on the root, which is NILL.
if (root == NILL)
return 0;
// The base case of the leaf node has a height equivalent to 1.
if (root.Lft == NILL && root.Rt == NILL)
return 1;
//If we find out the left subtree is not NILL; then we have to recursion for the right subtree.
if (root.Lft == NILL)
return minimumDepth(root.Rt) + 1;
//If we find out the right subtree is not NILL; then we have to recursion for the left subtree.
if (root.Rt == NILL)
return minimumDepth(root.Lft) + 1;
return Math.min(minimumDepth(root.Lft),
minimumDepth(root.Rt)) + 1;
}
// writing the main code
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new __nod(1);
tree.root.Lft = new __nod(2);
tree.root.Rt = new __nod(3);
tree.root.Lft.Lft = new __nod(4);
tree.root.Lft.Rt = new __nod(5);
System.out.println("The minimum depth of "+
"binary tree is : " + tree.minimumDepth());
}
}
Output

Example 4
using System;
// Creating a C# program or implementation to search and explore the minimum depth of a given binary tree.
/* Creating a new class that will have the left and right child of the current node and the key value. */
public class __nod
{
public int record;
public __nod Lft, Rt;
public __nod(int item)
{
record = item;
Lft = Rt = NILL;
}
}
public class BinaryTree
{
//Creating root for the BST
public __nod root;
public virtual int minimumDepth()
{
return minimumDepth(root);
}
/* creating a new function that will give us the minimum depth*/
public virtual int minimumDepth(__nod root)
{
// The case named corner shouldn't be called unless and until the code is called on the root, which is NILL.
if (root == NILL)
{
return 0;
}
// The base case of the leaf node has a height equivalent to 1.
if (root.Lft == NILL && root.Rt == NILL)
{
return 1;
}
//If we find out the left subtree is not NILL; then we have to recursion for the right subtree.
if (root.Lft == NILL)
{
return minimumDepth(root.Rt) + 1;
}
//If we find out the right subtree is not NILL; then we have to recursion for the left subtree.
if (root.Rt == NILL)
{
return minimumDepth(root.Lft) + 1;
}
return Math.Min(minimumDepth(root.Lft), minimumDepth(root.Rt)) + 1;
}
// writing the main code
public static void Main(string[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new __nod(1);
tree.root.Lft = new __nod(2);
tree.root.Rt = new __nod(3);
tree.root.Lft.Lft = new __nod(4);
tree.root.Lft.Rt = new __nod(5);
Console.WriteLine("The minimum depth of binary tree is : " + tree.minimumDepth());
}
}
Output
