Jobs

Interviews

Discussions

Minimum Absolute Difference in BST

Easy

Asked by:

32 views

Topics:

TreesRecursion

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

Input: root = [4,2,6,1,3]
Output: 1

Example 2:

Input: root = [1,0,48,null,null,12,49]
Output: 1

Constraints:

The number of nodes in the tree is in the range [2, 10⁴].
0 <= Node.val <= 10⁵

Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

Try coding it in LeetCode

Minimum Absolute Difference in BST

Easy

Asked by:

32 views

Topics:

TreesRecursion

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

Input: root = [4,2,6,1,3]
Output: 1

Example 2:

Input: root = [1,0,48,null,null,12,49]
Output: 1

Constraints:

The number of nodes in the tree is in the range [2, 10⁴].
0 <= Node.val <= 10⁵

Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

Try coding it in LeetCode

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 have?
Can the BST be empty or contain only one node?
Are duplicate values allowed in the BST, and if so, how should they be handled?
Is the given tree guaranteed to be a valid Binary Search Tree?
In the case of an empty tree or a single-node tree, what value should I return?

Brute Force Solution

Approach

The brute force method for finding the minimum absolute difference in a binary search tree involves checking every possible pair of node values. It's like comparing each person in a room with every other person to find the two closest in age, without any clever shortcuts.

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

First, gather all the values stored in each of the nodes of the tree into a simple list.
Then, take the first value in the list and calculate the difference between it and every other value in the list.
Remember the smallest difference you find.
Repeat this process for the second value in the list, comparing it to every other value, and update the smallest difference if you find an even smaller one.
Continue doing this for each value in the list, one by one, always comparing it to all the other values and keeping track of the smallest difference.
Once you've gone through all the values and compared them with all the others, the smallest difference you've kept track of is the answer.

Code Implementation

def minimum_absolute_difference_bst_brute_force(root):
    node_values = []

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

    inorder_traversal(root)
    minimum_difference = float('inf')

    # Iterate through all node values to calculate difference
    for first_index in range(len(node_values)):

        # Compare the first value with all others.
        for second_index in range(len(node_values)):
            if first_index != second_index:

                # Ensure we're only computing absolute differences.
                current_difference = abs(node_values[first_index] - node_values[second_index])

                # Update min difference if smaller value is found
                if current_difference < minimum_difference:
                    minimum_difference = current_difference

    return minimum_difference

Big(O) Analysis

Time Complexity

O(n²) – The algorithm first extracts all n node values from the BST into a list. Then, for each of the n values in the list, it calculates the absolute difference with every other value in the list. This involves a nested loop structure where for each of the n elements, the inner loop iterates through approximately n elements. Consequently, the total number of operations approximates n * n/2, which simplifies to a time complexity of O(n²).

Space Complexity

O(N) – The provided brute force approach first gathers all node values into a list. This list stores the values of each node in the binary search tree. If the BST has N nodes, the list will contain N elements. Therefore, the auxiliary space required is directly proportional to the number of nodes in the BST, resulting in O(N) space complexity.

Optimal Solution

Approach

The key to solving this problem efficiently lies in understanding the properties of a Binary Search Tree (BST). Since a BST is ordered, we can traverse the tree in a way that allows us to compare adjacent nodes and efficiently find the minimum difference.

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

Traverse the tree in an inorder fashion. Inorder traversal visits the left subtree, then the current node, and finally the right subtree. This guarantees we visit nodes in ascending order.
Keep track of the previously visited node. This allows us to compute the difference between the current node and its immediate predecessor.
Calculate the absolute difference between the current node's value and the value of the previous node.
Maintain a running minimum of these absolute differences. Whenever a smaller difference is found, update the minimum.
Continue the inorder traversal, updating the minimum difference along the way, until all nodes have been visited.
The final minimum difference is the smallest absolute difference between any two nodes in the BST.

Code Implementation

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

def get_minimum_difference(root):
    minimum_absolute_difference = float('inf')
    previous_node_value = None

    def inorder_traversal(node):
        nonlocal minimum_absolute_difference
        nonlocal previous_node_value

        if not node:
            return

        inorder_traversal(node.left)

        # Only calculate diff after first node
        if previous_node_value is not None:

            difference = abs(node.val - previous_node_value)

            # Update the minimum difference found
            minimum_absolute_difference = min(minimum_absolute_difference, difference)

        # Store current node value for next comp
        previous_node_value = node.val

        inorder_traversal(node.right)

    inorder_traversal(root)
    return minimum_absolute_difference

Big(O) Analysis

Time Complexity

O(n) – The algorithm performs an inorder traversal of the Binary Search Tree (BST). Inorder traversal visits each node in the BST exactly once. Therefore, if the BST contains n nodes, the traversal will perform a constant amount of work for each of the n nodes. As a result, the time complexity is directly proportional to the number of nodes, leading to a linear time complexity of O(n).

Space Complexity

O(H) – The space complexity is determined by the recursion stack used during the inorder traversal. In the worst-case scenario (a skewed tree), the recursion depth can be equal to the number of nodes, N. In a balanced BST, the recursion depth is logarithmic, specifically the height of the tree, denoted as H, where H is log(N). Therefore, the space complexity is O(H), representing the maximum depth of the recursion stack.

Edge Cases

Case	How to Handle
Null or empty tree	Return a large value like Integer.MAX_VALUE since no difference can be computed, or handle separately by returning a special value or throwing an exception if appropriate.
Tree with only one node	Return a large value like Integer.MAX_VALUE since no difference can be computed.
Tree with only two nodes	Directly compute the absolute difference between the two node values.
BST with all nodes having the same value	The minimum absolute difference will be 0, which the inorder traversal approach will find when comparing adjacent identical values.
Highly skewed BST (e.g., linked list)	Inorder traversal will still correctly find the minimum difference between adjacent nodes, but recursion depth could be a concern, suggesting iterative inorder traversal.
BST with negative node values	Absolute difference calculation handles negative numbers correctly.
Large range of node values (potential integer overflow)	Ensure that the absolute difference calculation uses long to prevent integer overflow issues.
Very large BST	The inorder traversal approach has O(N) time complexity and O(H) space complexity where H is height of the tree, which scales reasonably; however, for extremely deep trees, consider iterative inorder to reduce stack usage.

Null or empty tree

How to Handle:

Return a large value like Integer.MAX_VALUE since no difference can be computed, or handle separately by returning a special value or throwing an exception if appropriate.

Tree with only one node

How to Handle:

Return a large value like Integer.MAX_VALUE since no difference can be computed.

Tree with only two nodes

How to Handle:

Directly compute the absolute difference between the two node values.

BST with all nodes having the same value

How to Handle:

The minimum absolute difference will be 0, which the inorder traversal approach will find when comparing adjacent identical values.

Highly skewed BST (e.g., linked list)

How to Handle:

Inorder traversal will still correctly find the minimum difference between adjacent nodes, but recursion depth could be a concern, suggesting iterative inorder traversal.

BST with negative node values

How to Handle:

Absolute difference calculation handles negative numbers correctly.

Large range of node values (potential integer overflow)

How to Handle:

Ensure that the absolute difference calculation uses long to prevent integer overflow issues.

Very large BST

How to Handle:

The inorder traversal approach has O(N) time complexity and O(H) space complexity where H is height of the tree, which scales reasonably; however, for extremely deep trees, consider iterative inorder to reduce stack usage.

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 have?
Can the BST be empty or contain only one node?
Are duplicate values allowed in the BST, and if so, how should they be handled?
Is the given tree guaranteed to be a valid Binary Search Tree?
In the case of an empty tree or a single-node tree, what value should I return?

Brute Force Solution

Approach

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

First, gather all the values stored in each of the nodes of the tree into a simple list.
Then, take the first value in the list and calculate the difference between it and every other value in the list.
Remember the smallest difference you find.
Repeat this process for the second value in the list, comparing it to every other value, and update the smallest difference if you find an even smaller one.
Continue doing this for each value in the list, one by one, always comparing it to all the other values and keeping track of the smallest difference.
Once you've gone through all the values and compared them with all the others, the smallest difference you've kept track of is the answer.

Code Implementation

def minimum_absolute_difference_bst_brute_force(root):
    node_values = []

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

    inorder_traversal(root)
    minimum_difference = float('inf')

    # Iterate through all node values to calculate difference
    for first_index in range(len(node_values)):

        # Compare the first value with all others.
        for second_index in range(len(node_values)):
            if first_index != second_index:

                # Ensure we're only computing absolute differences.
                current_difference = abs(node_values[first_index] - node_values[second_index])

                # Update min difference if smaller value is found
                if current_difference < minimum_difference:
                    minimum_difference = current_difference

    return minimum_difference

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Traverse the tree in an inorder fashion. Inorder traversal visits the left subtree, then the current node, and finally the right subtree. This guarantees we visit nodes in ascending order.
Keep track of the previously visited node. This allows us to compute the difference between the current node and its immediate predecessor.
Calculate the absolute difference between the current node's value and the value of the previous node.
Maintain a running minimum of these absolute differences. Whenever a smaller difference is found, update the minimum.
Continue the inorder traversal, updating the minimum difference along the way, until all nodes have been visited.
The final minimum difference is the smallest absolute difference between any two nodes in the BST.

Code Implementation

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

def get_minimum_difference(root):
    minimum_absolute_difference = float('inf')
    previous_node_value = None

    def inorder_traversal(node):
        nonlocal minimum_absolute_difference
        nonlocal previous_node_value

        if not node:
            return

        inorder_traversal(node.left)

        # Only calculate diff after first node
        if previous_node_value is not None:

            difference = abs(node.val - previous_node_value)

            # Update the minimum difference found
            minimum_absolute_difference = min(minimum_absolute_difference, difference)

        # Store current node value for next comp
        previous_node_value = node.val

        inorder_traversal(node.right)

    inorder_traversal(root)
    return minimum_absolute_difference

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty tree	Return a large value like Integer.MAX_VALUE since no difference can be computed, or handle separately by returning a special value or throwing an exception if appropriate.
Tree with only one node	Return a large value like Integer.MAX_VALUE since no difference can be computed.
Tree with only two nodes	Directly compute the absolute difference between the two node values.
BST with all nodes having the same value	The minimum absolute difference will be 0, which the inorder traversal approach will find when comparing adjacent identical values.
Highly skewed BST (e.g., linked list)	Inorder traversal will still correctly find the minimum difference between adjacent nodes, but recursion depth could be a concern, suggesting iterative inorder traversal.
BST with negative node values	Absolute difference calculation handles negative numbers correctly.
Large range of node values (potential integer overflow)	Ensure that the absolute difference calculation uses long to prevent integer overflow issues.
Very large BST	The inorder traversal approach has O(N) time complexity and O(H) space complexity where H is height of the tree, which scales reasonably; however, for extremely deep trees, consider iterative inorder to reduce stack usage.

Null or empty tree

How to Handle:

Return a large value like Integer.MAX_VALUE since no difference can be computed, or handle separately by returning a special value or throwing an exception if appropriate.

Tree with only one node

How to Handle:

Return a large value like Integer.MAX_VALUE since no difference can be computed.

Tree with only two nodes

How to Handle:

Directly compute the absolute difference between the two node values.

BST with all nodes having the same value

How to Handle:

The minimum absolute difference will be 0, which the inorder traversal approach will find when comparing adjacent identical values.

Highly skewed BST (e.g., linked list)

How to Handle:

Inorder traversal will still correctly find the minimum difference between adjacent nodes, but recursion depth could be a concern, suggesting iterative inorder traversal.

BST with negative node values

How to Handle:

Absolute difference calculation handles negative numbers correctly.

Large range of node values (potential integer overflow)

How to Handle:

Ensure that the absolute difference calculation uses long to prevent integer overflow issues.

Very large BST

How to Handle: