Find Minimum Depth of a Binary Tree | C ++ program to find minimum depth of a given Binary Tree ; A Binary Tree Node ; A queue item ( Stores pointer to node and an integer ) ; Iterative method to find minimum depth of Binary Tree ; Corner Case ; Create an empty queue for level order traversal ; Enqueue Root and initialize depth as 1 ; Do level order traversal ; Remove the front queue item ; Get details of the remove item ; If this is the first leaf node seen so far Then return its depth as answer ; If left subtree is not NULL , add it to queue ; If right subtree is not NULL , add it to queue ; Utility function to create a new tree Node ; Driver program to test above functions ; Let us create binary tree shown in above diagram
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; struct qItem { Node * node ; int depth ; } ; int minDepth ( Node * root ) { if ( root == NULL ) return 0 ; queue < qItem > q ; qItem qi = { root , 1 } ; q . push ( qi ) ; while ( q . empty ( ) == false ) { qi = q . front ( ) ; q . pop ( ) ; Node * node = qi . node ; int depth = qi . depth ; if ( node -> left == NULL && node -> right == NULL ) return depth ; if ( node -> left != NULL ) { qi . node = node -> left ; qi . depth = depth + 1 ; q . push ( qi ) ; } if ( node -> right != NULL ) { qi . node = node -> right ; qi . depth = depth + 1 ; q . push ( qi ) ; } } return 0 ; } 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 -> left = newNode ( 4 ) ; root -> left -> right = newNode ( 5 ) ; cout << minDepth ( root ) ; return 0 ; }