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