a shot of dev knowledge

RELATED TAGS

How to find the minimum depth of a binary tree

The minimum depth of a binary tree is the number of nodes from the root node to the nearest leaf node.

Consider the binary tree below: The minimum depth of this tree is $3$; it is comprised of nodes 1, 2, and 4.

Let’s look at solutions to calculate the minimum depth of a given binary tree.

1. Recursive solution

The idea is to check if every node is a leaf node. If the current node is a leaf node, return $1$. Otherwise, if the node has no left sub-tree, then recur on the right sub-tree. Similarly, if the node has no right sub-tree, then recur on the left sub-tree. Finally, if a node has both left and right sub-trees, recur on both and return the minimum value.

Implementation

Using the binary tree illustrated above, the algorithm is implemented as follows:

#include <iostream>
using namespace std;

struct Node {
int value;
Node *left, *right;

Node(int val)
{
this->value = val;
this->left = this->right = NULL;
}
};

int minimumDepth(Node * curr)
{
// Null node has 0 depth.
if(!curr)
return 0;

// Leaf node reached.
if (curr->left == NULL && curr->right == NULL)
return 1;

// Current node has only right subtree.
if(!curr->left)
return 1 + minimumDepth(curr->right);

// Current node has only left subtree.
else if (!curr->right)
return 1 + minimumDepth(curr->left);

// if none of the above cases, then recur on both left and right subtrees.
return 1 + min(minimumDepth(curr->right),
minimumDepth(curr->left));
}

// driver code
int main() {
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(6);
root->right->right->left = new Node(8);
root->right->left->right = new Node(7);
cout << "The minumum depth is: " << minimumDepth(root) << endl;
}

2. Level order traversal solution

Since all the nodes are traversed in the recursive solution described above, it has a time complexity of $O(n)$. However, note​ that even if the minimum depth is found immediately after the root node, the rest of the binary tree is still traversed.

The algorithm can be optimized further using the idea behind level-order traversal. Before reading ahead, spend some time thinking​ about how a level-order traversal can be used to optimize the minimum depth’s calculation.

In the binary tree illustrated earlier, the algorithm would stop once we reached node 4, so there would be no need to traverse nodes 5, 6,7, and 8.

Implementation

#include <iostream>
#include <queue>
using namespace std;

struct Node {
int value;
Node *left, *right;

Node(int val)
{
this->value = val;
this->left = this->right = NULL;
}
};

struct queueItem {
Node * node;
int depth;
};

int minimumDepth(Node * root)
{
// No depth if root is NULL.
if (!root)
return 0;

// Initialise a queue of type "queueItem" defined above.
queue <queueItem> q;
// Push the root node into the queue with depth 1.
queueItem currItem = {root, 1};
q.push(currItem);

// Level order traversal algorithm:
while (!q.empty())
{
// Get the node at the front of the queue
currItem = q.front();
q.pop();

// Retreive the data of the node.
Node * node = currItem.node;
int depth = currItem.depth;

// If this is the first leaf node encountered,
// return its depth and terminate the algorithm.
if (node->left == NULL && node->right == NULL)
return depth;

// If left subtree exists, add it to queue
if (node->left != NULL)
{
queueItem newItem;
newItem.node = node->left;
newItem.depth = depth + 1;
q.push(newItem);
}

// If right subtree exists, add it to queue
if (node->right != NULL)
{
queueItem newItem;
newItem.node = node->right;
newItem.depth = depth + 1;
q.push(newItem);
}
}
}

// driver code
int main() {
Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(6);
root->right->right->left = new Node(8);
root->right->left->right = new Node(7);
cout << "The minumum depth is: " << minimumDepth(root) << endl;
}

RELATED TAGS

RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time 