Minimum Depth Of Binary Tree

To solve this coding challenge to find the minimum depth of a binary tree, we can use a recursive approach. This approach will involve checking if the binary tree is empty, then if the root node is a leaf node (having no children), and finally making recursive calls to find the minimum depths of the left and right subtrees.

Explanation

The minimum depth of a binary tree is the shortest path from the root node to a leaf node. A leaf node is defined as a node that doesn't have any children. The solution follows these steps:

1. Check if the tree is empty : If the root node is None, the tree is empty, and its minimum depth is 0.
2. Check if the root is a leaf : If the root node has no left and right children, it is a leaf node, and so the minimum depth is 1.
3. Check for existence of left and right children :
• If the left child is None but the right child exists, the minimum depth is the minimum depth of the right subtree plus 1.
• If the right child is None but the left child exists, the minimum depth is the minimum depth of the left subtree plus 1.
4. Recursive case : If both left and right children exist, find the minimum depth of both subtrees and add 1 to the minimum of these two values.

Step-by-Step Explanation / Detailed Steps in Pseudocode

5. Define the function to calculate minimum depth :
• If the input root node is null, return 0.
6. Check if the current node is a leaf node :
• If both left and right children are null, return 1.
7. Handle cases where one of the child nodes is absent :
• If the left child is null, call the function for the right subtree and add 1.
• If the right child is null, call the function for the left subtree and add 1.
8. Both children present :
• Call the function for both the left and right subtrees, find the minimum of these depths, and add 1.

Pseudocode with Comments

                                            
// Function to find the minimum depth of a binary tree
function findMinDepth(node) {
    // If the node is None, the tree is empty
    if (node is null) {
        return 0
    }
    
    // If the node is a leaf node (no children), the minimum depth is 1
    if (node.left is null and node.right is null) {
        return 1
    }

    // Case where only the right subtree exists
    if (node.left is null) {
        // Recur for the right child and add 1 to the result
        return 1 + findMinDepth(node.right)
    }
    
    // Case where only the left subtree exists
    if (node.right is null) {
        // Recur for the left child and add 1 to the result
        return 1 + findMinDepth(node.left)
    }

    // Recursive case where both subtrees exist
    // Find the minimum depth of both subtrees and add 1
    return 1 + min(findMinDepth(node.left), findMinDepth(node.right))
}

                                        

In this approach:

• The function
  findMinDepth()
  is called recursively for the left and right child nodes if they exist.
• The base cases where the node is null (indicating an empty tree) and where the node is a leaf node are handled first.
• Conditional checks determine if only one of the child nodes is present, where the function is called recursively on the existing child.
• If both child nodes are present, the minimum depth is determined by calling the function recursively on both child nodes and adding 1 to the minimal depth found.

This detailed methodology ensures that we navigate the tree efficiently and find the minimum depth as required.