How to find Minimum Depth of the Tree using DFS Recursion

The DFS algorithm (DFS Recursion) employs the concept of backtracking and is recursive. It entails thorough searches of all the nodes either by moving forward, if possible, or by going backwards.

Advertisement
Skip advert

When there are no more nodes along the current path and you are traveling ahead, the term “backtrack” refers to moving backwards along the same path in order to discover nodes to traverse. Until all of the unvisited nodes have been traveled, all of the nodes on the current path will be visited. At that point, the new path will be chosen.

Stacks can be used to implement DFS’s recursive nature. Here’s the fundamental concept:
Select a beginning node, then stack all of its neighboring nodes on top of it.
To choose the next node to visit, pop a node from the stack, and push all of its neighboring nodes into a stack.
Up till the stack is empty, repeat this step. Make sure the nodes that are visited are noted, though. You won’t be able to access the same node more than once as a result. If the nodes that are visited are not marked and a node is visited more than once, an infinite loop could result.

Advertisement
Skip advert
// Minimum Depth of the Tree using Recursion
class Solution {
public:
    int minDepth(TreeNode* root) {
        
        // Base case
        if(root == NULL){
            return 0;
        }
        
        int ans = 0;
        
        int leftHeight = minDepth(root -> left);
        int rightHeight = minDepth(root -> right);
        
        // TO HANDLE EDGE CASE FOR SECOND EXAMPLE IN WHICH HEIHGT OF LEFT = 0 AND
        // HEIGHT OF RIGHT = 5 BUT ANS IS 5 INSTEAD OF 0.
        
        // Coz we want to add count of root too, so that's why we added 1 in it.
        if(leftHeight == 0 && rightHeight != 0)
            ans = rightHeight + 1;
        else if(leftHeight != 0 && rightHeight == 0)
            ans = leftHeight + 1;
        else
            ans = min(leftHeight, rightHeight) + 1;
        
        return ans;

    }
};

All Credits goes to Harcharn Preet Singh

Leave a Reply

Your email address will not be published.