I am reading Binary Trees. while practicing coding problems I came across some solutions where it is asked to find Min Depth of Binary Tree. Now as per my understanding depth is no of edges from root to node (leaf node in case of leaf nodes / binary tree)
What is the min depth of Binary tree {1,2}
As per my solution it should be 1.
My tested solution
public int minDepth(TreeNode root) {
if(root == null){
return 0;
}
int ldepth = minDepth(root.left);
int rdepth = minDepth(root.right);
if(ldepth == 0){
return 1+rdepth;
}else if(rdepth == 0){
return 1+ldepth;
}
return (1 + Math.min(rdepth, ldepth));
}
Here, we calculate ldepth (minimum left subtree depth) and rdepth (minimum right subtree depth) for a node. Then, if ldepth is zero but rdepth is not, that means current node is not a leaf node, so return 1 + rdepth. If both rdepth and ldepth are zeros then still 'if' condition works as we return 1+0 for current leaf node.
Similar logic for 'else if' branch. In 'return' statement as both 'if' conditions has been failed we return 1 (current node) + minimum value of recursive calls to both left and right branch.
Remember a leaf node has neither left nor right child.
1
/
/
2
so here 2 is the leaf node but 1 is not. so minimum depth for this case is 2 assuming depth of root node is 1.
#include<vector>
#include<iostream>
#include<climits>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int minDepth(TreeNode *root) {
if(root == NULL) return 0;
return getDepth(root);
}
int getDepth(TreeNode *r ){
if(r == NULL) return INT_MAX;
if(r->left == NULL && r->right == NULL)
return 1;
return 1+ min(getDepth(r->left), getDepth(r->right));
}
};
A root node will have a depth of 0, so here depth of the given tree will be 1, refer below recursion and iterative solution to find min dept of binary tree.
Recursive solution :
public static int findMinDepth(BTNode root) {
if (root == null || (root.getLeft() == null && root.getRight() == null)) {
return 0;
}
int ldepth = findMinDepth(root.getLeft());
int rdepth = findMinDepth(root.getRight());
return (Math.min(rdepth + 1, ldepth + 1));
}
Iterative solution :
public static int minDepth(BTNode root) {
int minDepth = Integer.MAX_VALUE;
Stack<BTNode> nodes = new Stack<>();
Stack<BTNode> path = new Stack<>();
if (root == null) {
return -1;
}
nodes.push(root);
while (!nodes.empty()) {
BTNode node = nodes.peek();
if (!path.empty() && node == path.peek()) {
if (node.getLeft() == null && node.getRight() == null && path.size() <= minDepth) {
minDepth = path.size() - 1;
}
path.pop();
nodes.pop();
} else {
path.push(node);
if (node.getRight() != null) {
nodes.push(node.getRight());
}
if (node.getLeft() != null) {
nodes.push(node.getLeft());
}
}
}
return minDepth;
}
As others stated, solution should be 2... But it's semantic, you could simply take result and subtract 1 if your definition of depth is different.
Here's an iterative answer (in C#) (Rajesh Surana answer is a good Recusive answer):
public static int FindMinDepth<T>(BinarySearchTree<T> tree) where T : IComparable<T>
{
var current = tree._root;
int level = 0;
Queue<BSTNode<T>> q = new Queue<BSTNode<T>>();
if (current != null)
q.Enqueue(current);
while (q.Count > 0)
{
level++;
Queue<BSTNode<T>> nq = new Queue<BSTNode<T>>();
foreach (var element in q)
{
if (element.Left == null && element.Right == null)
return level;
if (element.Left != null) nq.Enqueue(element.Left);
if (element.Right != null) nq.Enqueue(element.Right);
}
q = nq;
}
return 0;
//throw new Exception("Min Depth not found!");
}
Given the following Binary Tree structure:
function BT(value, left = null, right = null) {
this.value = value;
this.left = left;
this.right = right;
}
A method to find the minimum depth can be something like so:
BT.prototype.getMinDepth = function() {
if (!this.value) {
return 0;
}
if (!this.left && !this.right) {
return 1;
}
if (this.left && this.right) {
return Math.min(this.left.getMinDepth(), this.right.getMinDepth()) + 1;
}
if (this.left) {
return this.left.getMinDepth() + 1;
}
if (this.right) {
return this.right.getMinDepth() + 1;
}
}
The time complexity of the above solution is O(n) as it traverses all the tree nodes.
A better runtime solution will be to use a breadth traversal method that ends when reaching the first leaf node:
BT.prototype.getMinDepth = function(depth = 0) {
if (!this.value) {
return depth;
}
depth++;
if (!this.left || !this.right) {
return depth;
}
return Math.min(this.left.getMinDepth(depth), this.right.getMinDepth(depth));
}
Given the depth of a path is the number of nodes from the root to the leaf node along this path. The minimum is the path with minimum number of nodes from the root to the LEAF node. In this case, the only leaf node is 2. (A leaf node is defined as a node with no children) Therefore, the only depth and also min depth is 2.
A sample code in Java:
public class Solution {
public int minDepth(TreeNode root) {
if (root==null) return 0;
if ((root.left==null) || (root.right==null)) {
return 1+Math.max(minDepth(root.left),minDepth(root.right));
}
return 1+Math.min(minDepth(root.left),minDepth(root.right));
}
}
Minimum depth is the minimum of the depth of leftsubtree and rightsubtree.
public static int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
return getDepth(root);
}
private static int getDepth(TreeNode a) {
if(a.left == null & a.right == null) {
return 1;
}
int leftDepth = 0;
int rightDepth = 0;
if(a.left != null) {
leftDepth = getDepth(a.left);
}
if(a.right != null) {
rightDepth = getDepth(a.right);
}
return (Math.min(leftDepth, rightDepth)+1);
}
The minDepth of a binary tree means the shortest distance from the root to a leaf node. Though it is arguable whether the minDepth of your binary tree is 1 or 2, depending on whether you want the shortest distance to a null node, in which case the answer would be 1 OR the shortest distance to a null node whose sibling is ALSO a null node, in which case the answer to Binary tree{1,2} would be 2. Generally, the former is asked, and following the algorithm mentioned in Cracking the Coding Interview , we have the solution as
int minDepth(TreeNode root) {
if (root == null) { return 0;}
return 1 + Math.min(minDepth(root.left), minDepth(root.right));
}
