MIN DEPTH OF BINARY TREE

By: Saurav

2018-01-17 23:46:00 UTC

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

NOTE : The path has to end on a leaf node.
Example :

1
/
2
min depth = 2.

InterviewBit

This problem is similar to the last problem but there is one twist and on the first try I also got it wrong. Notice that it says that we only have to consider the leaf nodes. So if there is a node where let's say, the right node is nil but there is a left subtree, we should not consider the right node and vice versa.

Algo:
Base case: if root if nil, return 0 and if root has no children, return 1

We need to add one extra check:
If left node is nil, return the right subtree result and if right node is nil, return the left subtree result
if both are present return the minimum of the two.

If we don't check if a node is a leaf node, the minimum will always return 1 if we encounter a node with either right or left children as nil (Which is what I did in the first try.)

Let's see in action:

 def minDepth(a)
        return 0 if !a
        return 1 if !a.left and !a.right
        
        if !a.left
            minDepth(a.right) + 1
        elsif !a.right
            minDepth(a.left) + 1
        else
            return [minDepth(a.left), minDepth(a.right)].min + 1
        end
        
        

    end

Looks good to me.


Let me know what you think!
twitter: sprakash24oct
linkedin

Owned & Maintained by Saurav Prakash

If you like what you see, you can help me cover server costs or buy me a cup of coffee though donation :)