Program to Find Minimum Depth of a Binary Tree

• Write a C program to find the minimum depth of a binary tree.
• Write a function to find length of path from root to closest leaf node.

Given a binary tree, we have to find the minimum depth of a binary tree. Minimum depth of a binary tree is the number of nodes in a path from root node to closest leaf node. In other word's, it is the length of the path from root node till lowest level leaf node.

---

Method 1

Algorithm to find minimum height of binary tree.
Let "node" be the pointer to the root node of a sub tree. This algorithm is similar to algorithm of finding height of tree, except here we are finding minimum height.

• if node is equal to NULL, return 0.
• If node is a leaf node return 1.
• Recursively, find minimum depth of left and right sub tree. Let it be leftMinDepth and rightMinDepth respoctively.
• To get the minimum height of tree rooted at node, we will take minimum of leftMinDepth and rightMinDepth and 1 for root node.

Time Complexity : O(n), as we are doing pre order traversal of tree only once.

---

C program to find minimum depth of a binary tree

#include <stdio.h>
#include <limits.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below tree
            1
           / \
         2    3
        / \    \
       4  5    6
      / \
     7  8
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);
 
    root->left = getNewNode(2);
    root->right = getNewNode(3);
 
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(5);
    root->right->right = getNewNode(6);
 
    root->left->left->left = getNewNode(7);
    root->left->left->right = getNewNode(8);
    
    return root;

}

/* Returns minimum of two number */
int getMin(int a, int b){
    if(a >= b)
        return b;
    return a;
}

/*
Returns minimum depth of a binary tree 
*/
int getMinimumDepth(struct node *root) {
 int leftMinDepth = INT_MAX, rightMinDepth = INT_MAX;
    /* Empty Tree */
    if (root == NULL)
        return 0;
 
    /* Leaf Node */
    if (root->left == NULL && root->right == NULL)
       return 1;
 
    /* Recursively find minimum depth of left and right sub tree */
    if(root->right != NULL)
       rightMinDepth = getMinimumDepth(root->right);

    if (root->left != NULL)
       leftMinDepth = getMinimumDepth(root->left);
    /* find minimum of left and right height and add 1 for root node */
    return getMin(rightMinDepth, leftMinDepth) + 1;
}

int main() {
    struct node *root = generateBTree();    
    
 printf("Minimum Depth : %d",getMinimumDepth(root));
    
    getchar();
    return 0; 
}

Output

Minimum Depth : 3

---

Method 2

In this algorithm, we will traverse the binary tree by keeping track of the levels of the node and closest leaf node found till now. Let "node" be the pointer to the root node of a sub tree at level L.

• If node is equal to NULL, return.
• If node is a leaf node, then check if it's level(L) is less than the level of closest leaf node found till now. If yes, then update closest leaf node to current node and return.
• Recursively traverse left and right subtree of node at level L+1.

Time Complexity : O(n), as we are doing pre order traversal of tree only once.

---

C program to find minimum depth of a binary tree

#include <stdio.h>
#include <limits.h>

struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below tree
            1
           / \
         2    3
        / \    \
       4  5    6
      / \
     7  8
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);
 
    root->left = getNewNode(2);
    root->right = getNewNode(3);
 
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(5);
    root->right->right = getNewNode(6);
 
    root->left->left->left = getNewNode(7);
    root->left->left->right = getNewNode(8);
    
    return root;

}

/* 
  Returns minimum depth of a binary tree. 
*/
void getMinimumTreeDepth(struct node* root, int currentLevel, int *minWidth) {
  /* Empty tree */
  if(root == NULL) {
      return;
  }  
  /* Leaf Node : Check if the level of current leaf node is 
  less than minimum width found till now. If true, update minWidth */
  if(root->left == NULL && root->right == NULL) {
     if(currentLevel < *minWidth) {
        *minWidth = currentLevel;
         return;
      }
  }
  /*
  Recursively call getMinimumTreeDepth left and right sub tree 
  */
  getMinimumTreeDepth(root->left, currentLevel+1, minWidth);
  getMinimumTreeDepth(root->right, currentLevel+1, minWidth);
}

int main() {
    struct node *root = generateBTree();    
    int minWidth = INT_MAX;
    
    getMinimumTreeDepth(root, 1, &minWidth);
    printf("Minimum Depth : %d", minWidth);
    
    getchar();
    return 0; 
}

Output

Minimum Depth : 3