Jobs

Interviews

Discussions

Minimum Depth of Binary Tree

Easy

Google

1 view

Topics:

TreesGraphs

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: A leaf is a node with no children.

For example:

Consider the following binary tree:

The minimum depth is 2 (the path 3 -> 9 or 3 -> 20).

Consider the following binary tree:

The minimum depth is 5 (the path 2 -> 3 -> 4 -> 5 -> 6).

Clarify any assumptions or constraints, such as:

Can the tree be empty (root is null)?
What is the expected behavior if the tree is skewed (only has left or right children)?

Write a function to determine the minimum depth of a given binary tree.

Minimum Depth of Binary Tree

Easy

Google

1 view

Topics:

TreesGraphs

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: A leaf is a node with no children.

For example:

Consider the following binary tree:

The minimum depth is 2 (the path 3 -> 9 or 3 -> 20).

Consider the following binary tree:

The minimum depth is 5 (the path 2 -> 3 -> 4 -> 5 -> 6).

Clarify any assumptions or constraints, such as:

Can the tree be empty (root is null)?
What is the expected behavior if the tree is skewed (only has left or right children)?

Write a function to determine the minimum depth of a given binary tree.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected behavior if the root is null? Should I return 0 or throw an exception?
Can I assume the binary tree nodes contain integer values, or could they be other data types?
Is a single node tree considered to have a depth of 0 or 1?
Could the tree be unbalanced, and if so, should I expect significantly different lengths for left and right subtrees?
By 'nearest leaf node', do you mean the closest leaf in terms of the number of edges, or is there some other definition?

Brute Force Solution

Approach

The brute force method to find the minimum depth of a tree is like exploring every possible path from the top (root) down to the bottom (leaves). We check each path individually to see how far it goes. Ultimately, we compare all path lengths to find the shortest one.

Here's how the algorithm would work step-by-step:

Begin at the very top of the tree, the root node.
Explore every possible path downwards, one step at a time, going to each possible branch.
Keep going down each path until you reach a 'leaf'. A leaf is a point where the path ends; there are no more branches to follow.
Once you hit a leaf, count how many steps it took to get there from the root. That's the depth of that particular path.
Remember the depth of that path.
Repeat this process for absolutely every single path from the root to a leaf in the entire tree.
Once you've checked every possible path and recorded their depths, compare all the depths you found.
The smallest depth you found from all the paths is the minimum depth of the entire tree.

Code Implementation

def minimum_depth_of_binary_tree_brute_force(root):
    if not root:
        return 0

    all_depths = []

    def calculate_depth(node, current_depth):
        # If we've reached a leaf node,
        # record the depth.
        if not node.left and not node.right:
            all_depths.append(current_depth)
            return

        # Recursively explore the left subtree
        # if it exists.
        if node.left:

            calculate_depth(node.left, current_depth + 1)

        # Recursively explore the right subtree
        # if it exists.
        if node.right:

            calculate_depth(node.right, current_depth + 1)

    # Start the depth calculation from the root node
    # with an initial depth of 1.
    calculate_depth(root, 1)

    # Return the minimum depth from the list of all depths
    # after checking all paths
    return min(all_depths)

Big(O) Analysis

Time Complexity

O(n) – The described brute force approach explores every possible path from the root to a leaf in the binary tree. In the worst-case scenario (e.g., a complete binary tree), we visit each node once. Since the number of nodes in a binary tree is 'n', where 'n' represents the number of nodes in the tree, the algorithm effectively processes each node in the tree once to find all paths and their depths. Therefore, the time complexity is directly proportional to the number of nodes, resulting in O(n).

Space Complexity

O(N) – The brute force approach described explores every path from the root to a leaf. In the worst-case scenario, such as a skewed tree, the recursion stack could grow to the height of the tree, which can be N, where N is the number of nodes in the tree. This happens because we are essentially performing a depth-first traversal. Therefore, the maximum auxiliary space used by the recursion stack is proportional to N, resulting in a space complexity of O(N).

Optimal Solution

Approach

We want to find the shortest path from the top of the tree to the nearest 'leaf' (a node with no children). The best way to do this is to explore the tree level by level, stopping as soon as we find a leaf.

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Look at all the nodes one level down. If any of them are leaves, we're done. The minimum depth is 2.
If we didn't find any leaves on the second level, look at all the nodes one level further down. If any of them are leaves, we're done. The minimum depth is 3.
Keep repeating this process, level by level, until we find the first leaf. The depth of that leaf is the minimum depth of the tree.
It's important to note that a node only counts as a leaf if it has no left and no right child. If it only has one child, it's not a leaf, and we must keep searching below it.

Code Implementation

from collections import deque

def minimum_depth_of_binary_tree(root):
    if not root:
        return 0

    queue = deque([(root, 1)])

    while queue:
        node, current_depth = queue.popleft()

        # Check if current node is a leaf
        if not node.left and not node.right:
            return current_depth

        # If there's a left child, add it to the queue
        if node.left:

            queue.append((node.left, current_depth + 1))

        # If there's a right child, add it to the queue
        if node.right:

            queue.append((node.right, current_depth + 1))

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

Big(O) Analysis

Time Complexity

O(n) – The provided solution uses a level-order (breadth-first) traversal. In the worst-case scenario, we might need to visit all nodes in the tree before encountering a leaf node. Since we are visiting each node at most once to determine if it's a leaf, where n is the number of nodes in the tree, the algorithm's time complexity is directly proportional to the number of nodes. Therefore, the time complexity is O(n).

Space Complexity

O(W) – The described level-by-level (breadth-first) approach implicitly uses a queue to store nodes at each level. In the worst-case scenario, the queue might hold all nodes at the widest level of the tree. Therefore, the auxiliary space is proportional to the maximum width (W) of the binary tree, where W can potentially be N (the total number of nodes in a complete binary tree). Thus, the space complexity is O(W).

Edge Cases

Case	How to Handle
Null or empty root node	Return 0 if the root is null, as an empty tree has a minimum depth of 0.
Tree with only a root node (no children)	Return 1 if the root has no children, as it represents a path of length 1.
Highly unbalanced tree (skewed left or right)	The algorithm should correctly traverse the longer path, correctly identifying when the shorter leaf is found and returning that minimum depth.
Tree with only left child nodes	The algorithm traverses to the left-most leaf and returns the depth.
Tree with only right child nodes	The algorithm traverses to the right-most leaf and returns the depth.
Large tree depth (potential stack overflow with recursive approaches)	Consider using iterative BFS (Breadth-First Search) to avoid exceeding recursion depth limits and memory constraints.
Tree with a mix of null and non-null children nodes at different levels	Ensure the algorithm correctly identifies leaf nodes (nodes with no children) and doesn't incorrectly terminate at a node with a null child.
Integer overflow for very deep trees if depth is stored as an integer	While highly unlikely, consider alternative data types with larger capacity if handling extremely deep trees is a requirement.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the expected behavior if the root is null? Should I return 0 or throw an exception?
Can I assume the binary tree nodes contain integer values, or could they be other data types?
Is a single node tree considered to have a depth of 0 or 1?
Could the tree be unbalanced, and if so, should I expect significantly different lengths for left and right subtrees?
By 'nearest leaf node', do you mean the closest leaf in terms of the number of edges, or is there some other definition?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Begin at the very top of the tree, the root node.
Explore every possible path downwards, one step at a time, going to each possible branch.
Keep going down each path until you reach a 'leaf'. A leaf is a point where the path ends; there are no more branches to follow.
Once you hit a leaf, count how many steps it took to get there from the root. That's the depth of that particular path.
Remember the depth of that path.
Repeat this process for absolutely every single path from the root to a leaf in the entire tree.
Once you've checked every possible path and recorded their depths, compare all the depths you found.
The smallest depth you found from all the paths is the minimum depth of the entire tree.

Code Implementation

def minimum_depth_of_binary_tree_brute_force(root):
    if not root:
        return 0

    all_depths = []

    def calculate_depth(node, current_depth):
        # If we've reached a leaf node,
        # record the depth.
        if not node.left and not node.right:
            all_depths.append(current_depth)
            return

        # Recursively explore the left subtree
        # if it exists.
        if node.left:

            calculate_depth(node.left, current_depth + 1)

        # Recursively explore the right subtree
        # if it exists.
        if node.right:

            calculate_depth(node.right, current_depth + 1)

    # Start the depth calculation from the root node
    # with an initial depth of 1.
    calculate_depth(root, 1)

    # Return the minimum depth from the list of all depths
    # after checking all paths
    return min(all_depths)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start at the very top of the tree.
Look at all the nodes one level down. If any of them are leaves, we're done. The minimum depth is 2.
If we didn't find any leaves on the second level, look at all the nodes one level further down. If any of them are leaves, we're done. The minimum depth is 3.
Keep repeating this process, level by level, until we find the first leaf. The depth of that leaf is the minimum depth of the tree.
It's important to note that a node only counts as a leaf if it has no left and no right child. If it only has one child, it's not a leaf, and we must keep searching below it.

Code Implementation

from collections import deque

def minimum_depth_of_binary_tree(root):
    if not root:
        return 0

    queue = deque([(root, 1)])

    while queue:
        node, current_depth = queue.popleft()

        # Check if current node is a leaf
        if not node.left and not node.right:
            return current_depth

        # If there's a left child, add it to the queue
        if node.left:

            queue.append((node.left, current_depth + 1))

        # If there's a right child, add it to the queue
        if node.right:

            queue.append((node.right, current_depth + 1))

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

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty root node	Return 0 if the root is null, as an empty tree has a minimum depth of 0.
Tree with only a root node (no children)	Return 1 if the root has no children, as it represents a path of length 1.
Highly unbalanced tree (skewed left or right)	The algorithm should correctly traverse the longer path, correctly identifying when the shorter leaf is found and returning that minimum depth.
Tree with only left child nodes	The algorithm traverses to the left-most leaf and returns the depth.
Tree with only right child nodes	The algorithm traverses to the right-most leaf and returns the depth.
Large tree depth (potential stack overflow with recursive approaches)	Consider using iterative BFS (Breadth-First Search) to avoid exceeding recursion depth limits and memory constraints.
Tree with a mix of null and non-null children nodes at different levels	Ensure the algorithm correctly identifies leaf nodes (nodes with no children) and doesn't incorrectly terminate at a node with a null child.
Integer overflow for very deep trees if depth is stored as an integer	While highly unlikely, consider alternative data types with larger capacity if handling extremely deep trees is a requirement.