Minimum Depth of Binary Tree Leetcode Solution  

Difficulty Level Easy
Frequently asked in Amazon Apple Facebook
algorithms Binary Tree Breadth First Search coding Depth First Search Interview interviewprep LeetCode LeetCodeSolutions

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.

Example  

Input

Minimum Depth of Binary Tree Leetcode SolutionPin

 

Please click Like if you loved this article?

 

 

 

 

 

 

2

Explanation

The Shortest path is: 2 -> 1 , which is of length 2

Input

 

 

 

 

 

Please click Like if you loved this article?

 

 

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 but as we have found no leaf in this subtree, so this will be a wrong answer. Hence, we only need to call the recursive function when the node it is called upon is NOT null.

See also
Three Consecutive Odds Leetcode Solution

Algorithm

  1. Create a function minDepth() to return the minimum depth of the passed root
  2. If the root is NULL, return
  3. In case both the left and right subtrees are NULL, return 1
  4. If the left subtree is NULL, return 1 + minDepth(root->right)
  5. Else if case the right subtree is NULL, return 1 + minDepth(root->left)
  6. 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.

See also
License Key Formatting Leetcode Solution

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

  1. If root is NULL, return
  2. Initialize a queue of pair of tree nodes and integers
  3. Push the root node to the queue with its depth as 1
  4. 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
  5. 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.

See also
Find any one of the multiple repeating elements in read only array

Space complexity

O(N), as we use a queue to store details of every node.

Please click Like if you loved this article?

1