Problem: Given a binary tree, find its minimum depth.
Minimum Depth: The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.(The node having 0 children is called leaf node).
Example 1:
Input: root = [2, 4, 5, 8, 11]
Output: 2
Output: 2
Code Implementation:
public class MinimumDepth {
static class Node {
int data;
Node left, right;
Node(int key) {
data = key;
left = right = null;
}
}
public static void main(String[] args) {
Node root = new Node(2);
root.left = new Node(4);
root.right = new Node(5);
root.left.left = new Node(8);
root.left.right = new Node(11);
System.out.println("Minimum Depth of Tree is: " + minDepth(root));
}
public static int minDepth(Node root) {
if (root == null)
return 0;
// this is the leaf node with no children
if (root.left == null && root.right == null)
return 1;
// if root.left is null go to right of root
if (root.left == null) {
return minDepth(root.right) + 1;
}
// if root.right is null go to left of tree
if (root.right == null) {
return minDepth(root.left) + 1;
}
// return the min height
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
}
Output:
Minimum Depth of Tree is: 2
Complexity Analysis:
Time Complexity: O(n), where n is the number of nodes in tree.
Space Complexity: Considering the stack space, if the tree is balanced then O(log n) and if tree is unbalanced then O(n).