algoadvance

The problem requires us to find the minimum depth of a binary tree. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
Return its minimum depth = 2.

Clarifying Questions

1. What should be the output if the tree is empty?
   • If the tree is empty, the minimum depth should be 0.
2. What is the expected input format?
   • The input will be the root of a binary tree node, where each node has properties val, left, and right.
3. Can the binary tree contain duplicate values?
   • Yes, the tree can contain duplicate values.

Strategy

1. Recursive Depth-First Search (DFS) Approach:
   • The algorithm will traverse the tree to find the minimum depth.
   • Base Case: If the current node is None, return 0 as this does not contribute to the depth.
   • If the node is a leaf (both left and right children are None), return 1.
   • Recursively find the minimum depth of the left subtree and the right subtree.
   • If one of the children is None, ignore it and return the depth of the non-None subtree.
   • Return the minimum of the left and right subtree depths plus 1 for the current node.

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def minDepth(root: TreeNode) -> int:
    if not root:
        return 0

    # If left subtree is None, then the minimum depth must be found in the right subtree
    if not root.left:
        return minDepth(root.right) + 1
    
    # If right subtree is None, then the minimum depth must be found in the left subtree
    if not root.right:
        return minDepth(root.left) + 1
    
    # If both subtree exists, find the minimal path from both subtrees
    return min(minDepth(root.left), minDepth(root.right)) + 1

Time Complexity

• The time complexity of this approach is O(N), where N is the number of nodes in the binary tree. This is because in the worst case, the algorithm will visit each node once.
• The space complexity is O(H), where H is the height of the tree. This is due to the recursion stack used during the depth-first traversal. In the worst-case scenario of a skewed tree, this could be O(N).

Feel free to ask if you need further clarifications or assistance!

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?