Jobs

Interviews

Discussions

Minimum Distance Between BST Nodes

Easy

Minimum Distance Between BST Nodes

Easy

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 range of values that the nodes in the BST can hold? Can they be negative or zero?
Can the BST be empty, or contain only one node? If so, what should the return value be?
Are there any duplicate values allowed in the BST? If so, how should they be handled when calculating the minimum distance?
Is the input guaranteed to be a valid Binary Search Tree?
Is the goal to minimize space complexity in addition to time complexity?

Brute Force Solution

Approach

To find the smallest difference between values in the tree, a brute force approach involves looking at every possible pair of values. We will find every value in the tree, then calculate the difference between each pair. We'll keep track of the smallest difference we've seen so far.

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

First, collect all the values that are stored in the tree.
Then, take the first value in the list and compare it to every other value in the list to find the difference between them.
Remember the smallest difference you find during these comparisons.
Move on to the second value in the list, and again, compare it to every other value to find the difference between them.
Update the smallest difference if you find a smaller one.
Repeat this process for every value in the list, comparing it with all the other values, and keeping track of the smallest difference found.
After comparing all possible pairs, the smallest difference you remembered is the answer.

Code Implementation

def minimum_distance_between_bst_nodes_brute_force(root):
    tree_values = []

    def inorder_traversal(node):
        if node:
            inorder_traversal(node.left)
            tree_values.append(node.val)
            inorder_traversal(node.right)

    inorder_traversal(root)

    # Initialize the minimum difference to a very large value.
    minimum_difference = float('inf')

    # Iterate through all possible pairs of nodes.
    for first_node_index in range(len(tree_values)):

        for second_node_index in range(first_node_index + 1, len(tree_values)):

            # Avoid comparing the same node with itself
            difference = abs(tree_values[first_node_index] - tree_values[second_node_index])

            # Update the minimum difference if a smaller difference is found.
            if difference < minimum_difference:
                minimum_difference = difference

    return minimum_difference

Big(O) Analysis

Time Complexity

O(n²) – The algorithm first traverses the binary search tree to collect all n node values into a list. Then, for each of the n elements in the list, it iterates through the remaining elements to calculate the absolute difference. This results in a nested loop structure where, for each element, we perform approximately n comparisons. Thus, the total number of comparisons approaches n * (n-1)/2, which simplifies to O(n²).

Space Complexity

O(N) – The brute force approach first collects all the values from the Binary Search Tree into a list. This list stores, at most, N values, where N is the total number of nodes in the tree. No other significant auxiliary space is used beyond this list. Therefore, the auxiliary space complexity is proportional to the number of nodes in the tree, which is O(N).

Optimal Solution

Approach

The key to solving this efficiently is to realize we don't need to compare every single pair of nodes in the tree. Because it's a Binary Search Tree, nodes are ordered, so we just need to look at adjacent nodes in the sorted order to find the minimum difference.

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

First, think about how you would visit the nodes of the tree in a way that gives you all the nodes in increasing order. This is called an in-order traversal.
As you visit each node in this in-order fashion, keep track of the value of the previously visited node.
For each node, calculate the difference between its value and the value of the previously visited node.
Keep track of the smallest difference you have found so far.
After you have visited all the nodes, the smallest difference you tracked is the answer.

Code Implementation

def minimum_distance_between_bst_nodes(root):
    minimum_difference = float('inf')
    previous_node_value = None

    def in_order_traversal(node):
        nonlocal minimum_difference
        nonlocal previous_node_value

        if not node:
            return

        in_order_traversal(node.left)

        # We're at the "current" node in sorted order
        if previous_node_value is not None:
            difference = abs(node.val - previous_node_value)

            # Update minimum distance
            minimum_difference = min(minimum_difference, difference)

        # Store the current node's value for the next comparison
        previous_node_value = node.val

        in_order_traversal(node.right)

    # Traverse the tree in-order to visit nodes in sorted order.
    in_order_traversal(root)

    return minimum_difference

Big(O) Analysis

Time Complexity

O(n) – The provided solution performs an in-order traversal of the Binary Search Tree. An in-order traversal visits each node exactly once. Therefore, the time complexity is directly proportional to the number of nodes (n) in the tree. Calculating the difference and updating the minimum difference are constant time operations performed for each node visited. Thus, the overall time complexity is O(n).

Space Complexity

O(H) – The in-order traversal described in the plain English explanation is typically implemented recursively. In the worst case, where the BST is skewed (e.g., a linked list), the depth of the recursion stack can reach the height H of the tree, requiring O(H) space to store the function call stack. This space is used for storing the return addresses and local variables for each recursive call. In the best and average cases for balanced trees, H is log(N), but the worst case is still O(H) where H can be equal to N. Other than the call stack, a few variables, such as the previously visited node's value and the minimum difference, are used, but they only require constant space. Thus, the overall auxiliary space complexity is O(H).

Edge Cases

Case	How to Handle
Null or empty BST	Return positive infinity as there's no distance to calculate.
BST with only one node	Return positive infinity because a minimum distance requires at least two nodes.
BST with only two nodes	Calculate the absolute difference between the two nodes' values directly.
BST with many nodes and very small minimum difference	The in-order traversal approach will find the smallest difference because it compares adjacent nodes in sorted order.
BST with nodes having duplicate values	The in-order traversal considers duplicates and calculates the distance which could be zero.
BST with integer values near the maximum/minimum integer limits (Integer Overflow)	Use long data type to store the node values or the absolute difference to prevent integer overflow during subtraction.
Highly skewed BST (essentially a linked list)	The in-order traversal will still find the minimum difference by comparing adjacent nodes after sorting.
BST where all node values are the same	The minimum difference between nodes would be zero as all adjacent nodes in the in-order traversal would have the same value.

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 range of values that the nodes in the BST can hold? Can they be negative or zero?
Can the BST be empty, or contain only one node? If so, what should the return value be?
Are there any duplicate values allowed in the BST? If so, how should they be handled when calculating the minimum distance?
Is the input guaranteed to be a valid Binary Search Tree?
Is the goal to minimize space complexity in addition to time complexity?

Brute Force Solution

Approach

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

First, collect all the values that are stored in the tree.
Then, take the first value in the list and compare it to every other value in the list to find the difference between them.
Remember the smallest difference you find during these comparisons.
Move on to the second value in the list, and again, compare it to every other value to find the difference between them.
Update the smallest difference if you find a smaller one.
Repeat this process for every value in the list, comparing it with all the other values, and keeping track of the smallest difference found.
After comparing all possible pairs, the smallest difference you remembered is the answer.

Code Implementation

def minimum_distance_between_bst_nodes_brute_force(root):
    tree_values = []

    def inorder_traversal(node):
        if node:
            inorder_traversal(node.left)
            tree_values.append(node.val)
            inorder_traversal(node.right)

    inorder_traversal(root)

    # Initialize the minimum difference to a very large value.
    minimum_difference = float('inf')

    # Iterate through all possible pairs of nodes.
    for first_node_index in range(len(tree_values)):

        for second_node_index in range(first_node_index + 1, len(tree_values)):

            # Avoid comparing the same node with itself
            difference = abs(tree_values[first_node_index] - tree_values[second_node_index])

            # Update the minimum difference if a smaller difference is found.
            if difference < minimum_difference:
                minimum_difference = difference

    return minimum_difference

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, think about how you would visit the nodes of the tree in a way that gives you all the nodes in increasing order. This is called an in-order traversal.
As you visit each node in this in-order fashion, keep track of the value of the previously visited node.
For each node, calculate the difference between its value and the value of the previously visited node.
Keep track of the smallest difference you have found so far.
After you have visited all the nodes, the smallest difference you tracked is the answer.

Code Implementation

def minimum_distance_between_bst_nodes(root):
    minimum_difference = float('inf')
    previous_node_value = None

    def in_order_traversal(node):
        nonlocal minimum_difference
        nonlocal previous_node_value

        if not node:
            return

        in_order_traversal(node.left)

        # We're at the "current" node in sorted order
        if previous_node_value is not None:
            difference = abs(node.val - previous_node_value)

            # Update minimum distance
            minimum_difference = min(minimum_difference, difference)

        # Store the current node's value for the next comparison
        previous_node_value = node.val

        in_order_traversal(node.right)

    # Traverse the tree in-order to visit nodes in sorted order.
    in_order_traversal(root)

    return minimum_difference

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty BST	Return positive infinity as there's no distance to calculate.
BST with only one node	Return positive infinity because a minimum distance requires at least two nodes.
BST with only two nodes	Calculate the absolute difference between the two nodes' values directly.
BST with many nodes and very small minimum difference	The in-order traversal approach will find the smallest difference because it compares adjacent nodes in sorted order.
BST with nodes having duplicate values	The in-order traversal considers duplicates and calculates the distance which could be zero.
BST with integer values near the maximum/minimum integer limits (Integer Overflow)	Use long data type to store the node values or the absolute difference to prevent integer overflow during subtraction.
Highly skewed BST (essentially a linked list)	The in-order traversal will still find the minimum difference by comparing adjacent nodes after sorting.
BST where all node values are the same	The minimum difference between nodes would be zero as all adjacent nodes in the in-order traversal would have the same value.