In this problem, we need to find the length of the shortest path from the root to any leaf in a given binary tree. Note that the “length of the path” here means the number of nodes from the root node to the leaf node. This length is called Minimum Depth of A Binary Tree.
Table of Contents
Example
Input
2
Explanation
The Shortest path is: 2 -> 1 , which is of length 2
Input
3
Explanation
The Shortest Path is: 1 -> 2 -> 3, of length 3
Approach(Recursive)
This problem is structurally same as finding the height of a binary tree but in this case, we need to find the minimum height/depth between the root and any leaf in the tree. We can retrieve the minimum depths of left and right subtrees of the root using Depth First Search(DFS) and then return the minimum of the two depths. We need to consider some cases when either of the left and right subtrees of a node is NULL. If the left subtree is NULL, it will return a height equal to 0 but as we have found no leaf in this subtree, so this 0 will be a wrong answer. Hence, we only need to call the recursive function when the node it is called upon is NOT null.
Algorithm
- Create a function minDepth() to return the minimum depth of the passed root
- If the root is NULL, return 0
- In case both the left and right subtrees are NULL, return 1
- If the left subtree is NULL, return 1 + minDepth(root->right)
- Else if case the right subtree is NULL, return 1 + minDepth(root->left)
- Return 1 + minimum(minDepth(root->left) , minDepth(root->right))
Implementation of Minimum Depth of Binary Tree Leetcode Solution
C++ Program
#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
int value;
treeNode *left , *right;
treeNode(int x)
{
value = x;
left = NULL;
right = NULL;
}
};
int minDepth(treeNode* root)
{
if(root == NULL)
return 0;
if(root->left == NULL && root->right == NULL)
return 1;
if(root->left == NULL)
return 1 + minDepth(root->right);
if(root->right == NULL)
return 1 + minDepth(root->left);
return 1 + min(minDepth(root->left) , minDepth(root->right));
}
int main()
{
treeNode* root = new treeNode(2);
root->left = new treeNode(1);
root->right = new treeNode(3);
root->right->left = new treeNode(4);
root->right->right = new treeNode(5);
cout << minDepth(root) << '\n';
}
Java Program
import java.util.*;
class treeNode
{
int value;
treeNode left, right;
public treeNode(int x)
{
value = x;
left = right = null;
}
}
class Pair
{
treeNode key;
int value;
Pair(treeNode root , int val)
{
key = root;
value = val;
}
}
class Minimum_Depth_Of_A_Binary_Tree
{
public static void main(String args[])
{
treeNode root = new treeNode(2);
root.left = new treeNode(1);
root.right = new treeNode(3);
root.right.left = new treeNode(4);
root.right.right = new treeNode(5);
System.out.println(minDepth(root));
}
static int minDepth(treeNode root)
{
if(root == null)
return 0;
if(root.left == null && root.right == null)
return 1;
if(root.left == null)
return 1 + minDepth(root.right);
if(root.right == null)
return 1 + minDepth(root.left);
return 1 + Math.min(minDepth(root.left) , minDepth(root.right));
}
}
2
Complexity Analysis of Minimum Depth of Binary Tree Leetcode Solution
Time Complexity
O(N), as we traverse the whole tree once even in the worst case.
Space complexity
O(N). When the binary tree is skewed, the recursive stack frames may consume upto O(N) space.
Approach(Iterative)
We can use Breadth-First Search(BFS) to find the first node which is a leaf and return its depth from the root. We can use a queue to store a pair of the nodes and their depths from the root node. As we receive a node which is a leaf, we return its depth.
Algorithm
- If root is NULL, return 0
- Initialize a queue of pair of tree nodes and integers
- Push the root node to the queue with its depth as 1
- While the queue is not empty:
- Retrieve the depth and node address of the front queue element
- Pop an item out of the queue
- If the front node is NULL, return its depth
- Push the left and right nodes to the tree if they are not null
- Return -1 to maintain syntax of the program as the function returns an integer
Implementation of Minimum Depth of Binary Tree Leetcode Solution
C++ Program
#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
int value;
treeNode *left , *right;
treeNode(int x)
{
value = x;
left = NULL;
right = NULL;
}
};
int minDepth(treeNode* root)
{
if(root == NULL)
return 0;
queue < pair <treeNode* , int> > q;
q.push({root , 1});
treeNode* frontNode;
int depth;
while(!q.empty())
{
frontNode = q.front().first;
depth = q.front().second;
q.pop();
if(frontNode->left == NULL && frontNode->right == NULL)
return depth;
if(frontNode->left != NULL)
q.push({frontNode->left , depth + 1});
if(frontNode->right != NULL)
q.push({frontNode->right , depth + 1});
}
return -1;
}
int main()
{
treeNode* root = new treeNode(2);
root->left = new treeNode(1);
root->right = new treeNode(3);
root->right->left = new treeNode(4);
root->right->right = new treeNode(5);
cout << minDepth(root) << '\n';
}
Java Program
import java.util.*;
class treeNode
{
int value;
treeNode left, right;
public treeNode(int x)
{
value = x;
left = right = null;
}
}
class Pair
{
treeNode key;
int value;
Pair(treeNode root , int val)
{
key = root;
value = val;
}
}
class Minimum_Depth_Of_A_Binary_Tree
{
public static void main(String args[])
{
treeNode root = new treeNode(2);
root.left = new treeNode(1);
root.right = new treeNode(3);
root.right.left = new treeNode(4);
root.right.right = new treeNode(5);
System.out.println(minDepth(root));
}
static int minDepth(treeNode root)
{
if(root == null)
return 0;
LinkedList <Pair> q = new LinkedList<>();
q.add(new Pair(root , 1));
treeNode frontNode;
int depth;
while(q.size() > 0)
{
frontNode = q.peek().key;
depth = q.peek().value;
q.remove();
if(frontNode.left == null && frontNode.right == null)
return depth;
if(frontNode.left != null)
q.add(new Pair(frontNode.left , depth + 1));
if(frontNode.right != null)
q.add(new Pair(frontNode.right , depth + 1));
}
return -1;
}
}
2
Complexity Analysis of Minimum Depth of Binary Tree Leetcode Solution
Time Complexity
O(N), as we traverse the whole tree once again.
Space complexity
O(N), as we use a queue to store details of every node.