Jobs

Interviews

Discussions

Closest Binary Search Tree Value

Easy

Asked by:

More companies

39 views

Topics:

Binary SearchTrees

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.

You are guaranteed to have only one unique value in the BST that is closest to the target.

Example 1:


Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

Example 2:


Input: root = [1], target = 4.428571
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
0 <= Node.val <= 10⁹
-10⁹ <= target <= 10⁹

Try coding it in LeetCode

Closest Binary Search Tree Value

Easy

Asked by:

39 views

Topics:

Binary SearchTrees

Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target.

You are guaranteed to have only one unique value in the BST that is closest to the target.

Example 1:


Input: root = [4,2,5,1,3], target = 3.714286
Output: 4

Example 2:


Input: root = [1], target = 4.428571
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
0 <= Node.val <= 10⁹
-10⁹ <= target <= 10⁹

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 data type of the 'target' value, and can it be outside the range of values present in the BST?
Can the BST be empty or contain null nodes?
If there are multiple nodes with the same minimum difference to the target, which node should be returned?
Is the given tree guaranteed to be a valid Binary Search Tree?
What is the range of values for the nodes in the BST?

Brute Force Solution

Approach

We want to find the value in the tree that's closest to a given target value. The brute force way to do this is to look at every single value in the tree and compare it to the target. Then we just pick the value that's closest.

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

First, get all the values from the tree.
Then, for each of those values, find the difference between it and the target value.
Keep track of which value has the smallest difference so far.
After checking every value in the tree, the one with the smallest difference is the answer.

Code Implementation

def closest_value_brute_force(root, target):

    tree_values = []

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

    # Extract all the values from the BST into a list
    inorder_traversal(root)

    closest_value = tree_values[0]
    min_difference = abs(tree_values[0] - target)

    for current_value in tree_values[1:]:
        # Calculate the absolute difference to find closest
        current_difference = abs(current_value - target)

        # Update if we've found a closer value
        if current_difference < min_difference:

            min_difference = current_difference

            closest_value = current_value

    return closest_value

Big(O) Analysis

Time Complexity

O(n) – The algorithm first traverses the entire binary search tree to collect all n values. This traversal takes O(n) time. Then, it iterates through the n collected values to find the closest one to the target, which takes another O(n) time. Therefore, the overall time complexity is O(n) + O(n), which simplifies to O(n).

Space Complexity

O(N) – The described brute force approach first gathers all the values from the binary search tree into a collection, implying the creation of an auxiliary data structure, such as a list or array, to store these values. In the worst case, this collection will contain all N nodes of the tree, where N is the total number of nodes in the BST. The space used for storing the differences between the target value and each node's value is constant. Thus, the dominant space usage is the auxiliary collection of size N, resulting in O(N) space complexity.

Optimal Solution

Approach

The problem asks us to find the node in a binary search tree that is closest to a given target value. We can efficiently find this value by leveraging the properties of a binary search tree to eliminate large portions of the tree from our search.

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

Start at the root of the tree.
Compare the target value to the value of the current node.
If the target value is smaller than the current node's value, go to the left child. This is because all values in the left subtree are smaller, so the closest value must be somewhere there.
If the target value is larger than the current node's value, go to the right child. This is because all values in the right subtree are larger, so the closest value must be somewhere there.
At each step, keep track of the node you've seen that's closest to the target so far.
Continue traversing the tree until you reach a point where you can't go any further (you hit an empty node).
The closest node that you kept track of during the traversal is the closest value in the tree to the target value.

Code Implementation

def find_closest_value_in_bst(tree_node, target):
    closest_value = tree_node.val
    current_node = tree_node

    while current_node:
        # Keep track of the closest value so far.
        if abs(target - current_node.val) < abs(target - closest_value):
            closest_value = current_node.val

        # Traverse left if the target is smaller.
        if target < current_node.val:
            current_node = current_node.left

        # Traverse right if the target is bigger.
        elif target > current_node.val:
            current_node = current_node.right

        # Target matches current node; it's the closest.
        else:
            return current_node.val

    return closest_value

Big(O) Analysis

Time Complexity

O(log n) – The algorithm traverses the binary search tree, moving either to the left or right child at each step. Because it's a binary search tree, each move eliminates half of the remaining search space. In the best and average case, this leads to a logarithmic traversal, proportional to the height of the tree, which is log n where n is the number of nodes. In the worst case, if the tree is skewed, it could degrade to O(n). However, assuming a balanced BST, the time complexity is O(log n).

Space Complexity

O(1) – The provided algorithm iteratively traverses the binary search tree. It maintains a single variable to track the closest value seen so far. No auxiliary data structures like arrays, hash maps, or stacks are used that scale with the input size N (number of nodes in the tree). Therefore, the algorithm uses a constant amount of extra space, independent of the input size.

Edge Cases

Case	How to Handle
Empty tree (root is null)	Return null or throw an exception if no valid node can be found in an empty tree.
Tree with only the root node	Return the root node's value directly as it's the closest.
Target value is smaller than the smallest value in the tree	Traverse to the leftmost leaf and return its value.
Target value is larger than the largest value in the tree	Traverse to the rightmost leaf and return its value.
BST contains duplicate values	The standard BST traversal handles duplicates without issue in finding the closest value.
Target is exactly the value of a node in the BST	Return the node's value immediately as it's the closest.
Integer overflow if target is very large and node values are very small or vice versa	Use long data type for difference calculations to avoid potential overflow.
Large BST with highly skewed distribution (e.g., almost a linked list)	An iterative approach is generally preferred to a recursive one in very deep trees to avoid stack overflow.

Empty tree (root is null)

How to Handle:

Return null or throw an exception if no valid node can be found in an empty tree.

Tree with only the root node

How to Handle:

Return the root node's value directly as it's the closest.

Target value is smaller than the smallest value in the tree

How to Handle:

Traverse to the leftmost leaf and return its value.

Target value is larger than the largest value in the tree

How to Handle:

Traverse to the rightmost leaf and return its value.

BST contains duplicate values

How to Handle:

The standard BST traversal handles duplicates without issue in finding the closest value.

Target is exactly the value of a node in the BST

How to Handle:

Return the node's value immediately as it's the closest.

Integer overflow if target is very large and node values are very small or vice versa

How to Handle:

Use long data type for difference calculations to avoid potential overflow.

Large BST with highly skewed distribution (e.g., almost a linked list)

How to Handle:

An iterative approach is generally preferred to a recursive one in very deep trees to avoid stack overflow.

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 data type of the 'target' value, and can it be outside the range of values present in the BST?
Can the BST be empty or contain null nodes?
If there are multiple nodes with the same minimum difference to the target, which node should be returned?
Is the given tree guaranteed to be a valid Binary Search Tree?
What is the range of values for the nodes in the BST?

Brute Force Solution

Approach

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

First, get all the values from the tree.
Then, for each of those values, find the difference between it and the target value.
Keep track of which value has the smallest difference so far.
After checking every value in the tree, the one with the smallest difference is the answer.

Code Implementation

def closest_value_brute_force(root, target):

    tree_values = []

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

    # Extract all the values from the BST into a list
    inorder_traversal(root)

    closest_value = tree_values[0]
    min_difference = abs(tree_values[0] - target)

    for current_value in tree_values[1:]:
        # Calculate the absolute difference to find closest
        current_difference = abs(current_value - target)

        # Update if we've found a closer value
        if current_difference < min_difference:

            min_difference = current_difference

            closest_value = current_value

    return closest_value

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start at the root of the tree.
Compare the target value to the value of the current node.
If the target value is smaller than the current node's value, go to the left child. This is because all values in the left subtree are smaller, so the closest value must be somewhere there.
If the target value is larger than the current node's value, go to the right child. This is because all values in the right subtree are larger, so the closest value must be somewhere there.
At each step, keep track of the node you've seen that's closest to the target so far.
Continue traversing the tree until you reach a point where you can't go any further (you hit an empty node).
The closest node that you kept track of during the traversal is the closest value in the tree to the target value.

Code Implementation

def find_closest_value_in_bst(tree_node, target):
    closest_value = tree_node.val
    current_node = tree_node

    while current_node:
        # Keep track of the closest value so far.
        if abs(target - current_node.val) < abs(target - closest_value):
            closest_value = current_node.val

        # Traverse left if the target is smaller.
        if target < current_node.val:
            current_node = current_node.left

        # Traverse right if the target is bigger.
        elif target > current_node.val:
            current_node = current_node.right

        # Target matches current node; it's the closest.
        else:
            return current_node.val

    return closest_value

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty tree (root is null)	Return null or throw an exception if no valid node can be found in an empty tree.
Tree with only the root node	Return the root node's value directly as it's the closest.
Target value is smaller than the smallest value in the tree	Traverse to the leftmost leaf and return its value.
Target value is larger than the largest value in the tree	Traverse to the rightmost leaf and return its value.
BST contains duplicate values	The standard BST traversal handles duplicates without issue in finding the closest value.
Target is exactly the value of a node in the BST	Return the node's value immediately as it's the closest.
Integer overflow if target is very large and node values are very small or vice versa	Use long data type for difference calculations to avoid potential overflow.
Large BST with highly skewed distribution (e.g., almost a linked list)	An iterative approach is generally preferred to a recursive one in very deep trees to avoid stack overflow.

Empty tree (root is null)

How to Handle:

Return null or throw an exception if no valid node can be found in an empty tree.

Tree with only the root node

How to Handle:

Return the root node's value directly as it's the closest.

Target value is smaller than the smallest value in the tree

How to Handle:

Traverse to the leftmost leaf and return its value.

Target value is larger than the largest value in the tree

How to Handle:

Traverse to the rightmost leaf and return its value.

BST contains duplicate values

How to Handle:

The standard BST traversal handles duplicates without issue in finding the closest value.

Target is exactly the value of a node in the BST

How to Handle:

Return the node's value immediately as it's the closest.

Integer overflow if target is very large and node values are very small or vice versa

How to Handle:

Use long data type for difference calculations to avoid potential overflow.

Large BST with highly skewed distribution (e.g., almost a linked list)

How to Handle:

An iterative approach is generally preferred to a recursive one in very deep trees to avoid stack overflow.