Jobs

Interviews

Discussions

Closest Binary Search Tree Value II

Hard

Asked by:

25 views

Topics:

TreesBinary SearchStacks

Given the root of a binary search tree, a target value target, and an integer k, return the k values in the BST that are closest to the target.

You should return the answer sorted from the smallest to the largest value.

Example 1:

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

Example 2:

Input: root = [1], target = 0.000000, k = 1
Output: [1]

Constraints:

The number of nodes in the tree is n.
1 <= k <= n <= 10⁴
0 <= Node.val <= 10⁹
-10⁹ <= target <= 10⁹

Follow up:

Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

Try coding it in LeetCode

Closest Binary Search Tree Value II

Hard

Asked by:

25 views

Topics:

TreesBinary SearchStacks

Given the root of a binary search tree, a target value target, and an integer k, return the k values in the BST that are closest to the target.

You should return the answer sorted from the smallest to the largest value.

Example 1:

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

Example 2:

Input: root = [1], target = 0.000000, k = 1
Output: [1]

Constraints:

The number of nodes in the tree is n.
1 <= k <= n <= 10⁴
0 <= Node.val <= 10⁹
-10⁹ <= target <= 10⁹

Follow up:

Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total 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 for nodes in the BST and the target value?
Can the input BST be empty or contain only one node?
If the target value is equal to a node's value, should that node's value be included in the result?
What should I return if the input BST contains fewer than k nodes?
In the case of ties (multiple values equally close to the target), is there a specific order I should return them in?

Brute Force Solution

Approach

The goal is to find the 'k' closest values to a target value in a binary search tree. The brute force method explores all possible values in the tree and picks the best ones.

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

First, gather all the values from the binary search tree into one big group.
Then, for every value in the group, calculate its distance from the target value.
After calculating the distances, sort all the values by their distance from the target value from closest to farthest.
Finally, pick the first 'k' values from the sorted list; these are the 'k' values closest to the target.

Code Implementation

def closest_binary_search_tree_value_ii_brute_force(root, target, k):
    all_values = []

    def inorder_traversal(node):
        if not node:
            return
        inorder_traversal(node.left)
        all_values.append(node.val)
        inorder_traversal(node.right)

    inorder_traversal(root)

    # Collect all values from the BST using inorder traversal.

    value_distance_pairs = []
    for value in all_values:
        distance = abs(value - target)
        value_distance_pairs.append((distance, value))

    # Calculate distances of each value from the target.

    value_distance_pairs.sort()

    # Sort values based on their distances to target

    closest_values = []
    for i in range(k):
        closest_values.append(value_distance_pairs[i][1])

    # Extract the k closest values.

    return closest_values

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm first traverses the entire binary search tree to collect all n values. This traversal takes O(n) time. Then, it calculates the absolute difference between each of the n values and the target, which takes O(n) time. The dominant operation is sorting the n values based on their distance from the target, which takes O(n log n) time using an efficient sorting algorithm like merge sort or quicksort. Finally, selecting the first k values takes O(k) time; since k <= n, it's bounded by O(n log n).

Space Complexity

O(N) – The algorithm first gathers all N values from the binary search tree into a single list. This list stores the tree's values, thus requiring space proportional to the number of nodes in the tree, N. Sorting this list requires additional space, which can be O(N) depending on the sorting algorithm used (e.g., merge sort). Therefore, the dominant space usage comes from storing all values in the temporary list, resulting in O(N) space complexity.

Optimal Solution

Approach

The task is to find the 'k' closest values to a target value in a binary search tree. Instead of looking at every single node, we can use the properties of a binary search tree to efficiently narrow down our search and maintain a running list of the closest values.

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

Start by finding the node in the tree that is closest to the target value.
Create a list to store the 'k' closest values that we'll find.
Add the closest node to our list.
We need to expand our search in both directions from the starting node. To do this, imagine two pointers: one moving towards smaller values and one moving towards larger values.
Compare the potential next closest values in each direction. Whichever is closer to the target, add it to our list.
Move the corresponding pointer in that direction to explore new potential candidates.
Repeat the comparison and pointer movement until we have 'k' values in our list.

Code Implementation

def find_closest_elements(root, target, k):
    closest_values = []

    def inorder(node):
        if not node:
            return []
        return inorder(node.left) + [node.val] + inorder(node.right)

    inorder_list = inorder(root)

    # Find the element closest to the target
    closest_element_index = min(range(len(inorder_list)), key=lambda i: abs(inorder_list[i] - target))
    closest_values.append(inorder_list[closest_element_index])

    left_pointer = closest_element_index - 1
    right_pointer = closest_element_index + 1

    while len(closest_values) < k:
        # Handle edge cases where one pointer goes out of bounds
        if left_pointer < 0:
            closest_values.append(inorder_list[right_pointer])
            right_pointer += 1
        elif right_pointer >= len(inorder_list):
            closest_values.append(inorder_list[left_pointer])
            left_pointer -= 1
        else:
            # Compare distances to decide which pointer to move
            if abs(inorder_list[left_pointer] - target) < abs(inorder_list[right_pointer] - target):
                closest_values.append(inorder_list[left_pointer])
                left_pointer -= 1
            else:
                closest_values.append(inorder_list[right_pointer])
                right_pointer += 1

    return closest_values

Big(O) Analysis

Time Complexity

O(k + h) – Finding the initial closest node in the BST takes O(h) time, where h is the height of the tree. After finding the closest node, we need to find the k closest values. The two pointers conceptually explore the tree to find these k closest values. In the worst case, these pointers might traverse nodes across multiple branches of the tree. Therefore, the time complexity is dominated by O(k) traversals to get k closest elements combined with initial O(h) to find the closest node. As a result, the overall time complexity is O(k + h).

Space Complexity

O(H + k) – The algorithm maintains a list of size 'k' to store the closest values. In the worst-case scenario where the BST is skewed, finding the initial closest node might require traversing the height 'H' of the tree using recursion, contributing to the call stack space. While not explicitly mentioned, the traversal to find predecessors and successors often uses iterative in-order traversal (simulated using stacks) which in the worst case can reach O(H) stack frames as well. Thus, the total auxiliary space used is O(H + k), where H is the height of the tree and k is the number of closest values to find.

Edge Cases

Case	How to Handle
Empty Tree	Return an empty list if the tree is null, as there are no nodes to process.
Target value smaller than all nodes in the tree	Return the 'k' smallest nodes from the tree in ascending order.
Target value larger than all nodes in the tree	Return the 'k' largest nodes from the tree in descending order.
Tree with only one node	Return a list containing only that node's value if k=1, otherwise handle according to k's size.
k is greater than the number of nodes in the tree	Return all nodes in the tree, sorted by their proximity to the target.
Tree contains duplicate values	The in-order traversal will handle duplicates correctly, as we consider all nodes regardless of value.
Integer Overflow if nodes have very large values and target is also large	Use long type for intermediate calculations of differences to prevent overflow during absolute difference computation.
k is zero or negative	Return an empty list if k is zero or negative since no elements are required.

Empty Tree

How to Handle:

Return an empty list if the tree is null, as there are no nodes to process.

Target value smaller than all nodes in the tree

How to Handle:

Return the 'k' smallest nodes from the tree in ascending order.

Target value larger than all nodes in the tree

How to Handle:

Return the 'k' largest nodes from the tree in descending order.

Tree with only one node

How to Handle:

Return a list containing only that node's value if k=1, otherwise handle according to k's size.

k is greater than the number of nodes in the tree

How to Handle:

Return all nodes in the tree, sorted by their proximity to the target.

Tree contains duplicate values

How to Handle:

The in-order traversal will handle duplicates correctly, as we consider all nodes regardless of value.

Integer Overflow if nodes have very large values and target is also large

How to Handle:

Use long type for intermediate calculations of differences to prevent overflow during absolute difference computation.

k is zero or negative

How to Handle:

Return an empty list if k is zero or negative since no elements are required.

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 for nodes in the BST and the target value?
Can the input BST be empty or contain only one node?
If the target value is equal to a node's value, should that node's value be included in the result?
What should I return if the input BST contains fewer than k nodes?
In the case of ties (multiple values equally close to the target), is there a specific order I should return them in?

Brute Force Solution

Approach

The goal is to find the 'k' closest values to a target value in a binary search tree. The brute force method explores all possible values in the tree and picks the best ones.

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

First, gather all the values from the binary search tree into one big group.
Then, for every value in the group, calculate its distance from the target value.
After calculating the distances, sort all the values by their distance from the target value from closest to farthest.
Finally, pick the first 'k' values from the sorted list; these are the 'k' values closest to the target.

Code Implementation

def closest_binary_search_tree_value_ii_brute_force(root, target, k):
    all_values = []

    def inorder_traversal(node):
        if not node:
            return
        inorder_traversal(node.left)
        all_values.append(node.val)
        inorder_traversal(node.right)

    inorder_traversal(root)

    # Collect all values from the BST using inorder traversal.

    value_distance_pairs = []
    for value in all_values:
        distance = abs(value - target)
        value_distance_pairs.append((distance, value))

    # Calculate distances of each value from the target.

    value_distance_pairs.sort()

    # Sort values based on their distances to target

    closest_values = []
    for i in range(k):
        closest_values.append(value_distance_pairs[i][1])

    # Extract the k closest values.

    return closest_values

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by finding the node in the tree that is closest to the target value.
Create a list to store the 'k' closest values that we'll find.
Add the closest node to our list.
We need to expand our search in both directions from the starting node. To do this, imagine two pointers: one moving towards smaller values and one moving towards larger values.
Compare the potential next closest values in each direction. Whichever is closer to the target, add it to our list.
Move the corresponding pointer in that direction to explore new potential candidates.
Repeat the comparison and pointer movement until we have 'k' values in our list.

Code Implementation

def find_closest_elements(root, target, k):
    closest_values = []

    def inorder(node):
        if not node:
            return []
        return inorder(node.left) + [node.val] + inorder(node.right)

    inorder_list = inorder(root)

    # Find the element closest to the target
    closest_element_index = min(range(len(inorder_list)), key=lambda i: abs(inorder_list[i] - target))
    closest_values.append(inorder_list[closest_element_index])

    left_pointer = closest_element_index - 1
    right_pointer = closest_element_index + 1

    while len(closest_values) < k:
        # Handle edge cases where one pointer goes out of bounds
        if left_pointer < 0:
            closest_values.append(inorder_list[right_pointer])
            right_pointer += 1
        elif right_pointer >= len(inorder_list):
            closest_values.append(inorder_list[left_pointer])
            left_pointer -= 1
        else:
            # Compare distances to decide which pointer to move
            if abs(inorder_list[left_pointer] - target) < abs(inorder_list[right_pointer] - target):
                closest_values.append(inorder_list[left_pointer])
                left_pointer -= 1
            else:
                closest_values.append(inorder_list[right_pointer])
                right_pointer += 1

    return closest_values

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty Tree	Return an empty list if the tree is null, as there are no nodes to process.
Target value smaller than all nodes in the tree	Return the 'k' smallest nodes from the tree in ascending order.
Target value larger than all nodes in the tree	Return the 'k' largest nodes from the tree in descending order.
Tree with only one node	Return a list containing only that node's value if k=1, otherwise handle according to k's size.
k is greater than the number of nodes in the tree	Return all nodes in the tree, sorted by their proximity to the target.
Tree contains duplicate values	The in-order traversal will handle duplicates correctly, as we consider all nodes regardless of value.
Integer Overflow if nodes have very large values and target is also large	Use long type for intermediate calculations of differences to prevent overflow during absolute difference computation.
k is zero or negative	Return an empty list if k is zero or negative since no elements are required.

Empty Tree

How to Handle:

Return an empty list if the tree is null, as there are no nodes to process.

Target value smaller than all nodes in the tree

How to Handle:

Return the 'k' smallest nodes from the tree in ascending order.

Target value larger than all nodes in the tree

How to Handle:

Return the 'k' largest nodes from the tree in descending order.

Tree with only one node

How to Handle:

Return a list containing only that node's value if k=1, otherwise handle according to k's size.

k is greater than the number of nodes in the tree

How to Handle:

Return all nodes in the tree, sorted by their proximity to the target.

Tree contains duplicate values

How to Handle:

The in-order traversal will handle duplicates correctly, as we consider all nodes regardless of value.

Integer Overflow if nodes have very large values and target is also large

How to Handle:

Use long type for intermediate calculations of differences to prevent overflow during absolute difference computation.

k is zero or negative

How to Handle:

Return an empty list if k is zero or negative since no elements are required.