Find the Closest Value in a Binary Search Tree

Question

The candidate is asked to find the closest value to a given target in a binary search tree (BST).

Codemia · Accepted Answer

To find the closest value to the target in a binary search tree, we can leverage the properties of the BST. Since the left child is always less than the parent node and the right child is always greater, we can traverse the tree starting from the root. At each node, we compare the current node's value to the target and decide whether to move left or right based on this comparison.

We will use a recursive function to traverse the tree. The function will keep track of the closest value found so far. If the current node's value is closer to the target than the closest value, we update the closest value. We then decide to continue the search either in the left or right subtree based on the comparison of the current node's value and the target.

Here is the Python code implementing this algorithm:
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def findClosestValueInBST(root, target):
    closest = root.val

def dfs(node):
        nonlocal closest
        if not node:
            return
        if abs(node.val - target) < abs(closest - target):
            closest = node.val
        if target < node.val:
            dfs(node.left)
        else:
            dfs(node.right)

dfs(root)
    return closest
```

The time complexity of this approach is O(h), where h is the height of the tree. In the worst case, we may have to traverse from the root to a leaf node. The space complexity is O(1) for the iterative approach or O(h) for the recursive stack if we implement it recursively.

We should consider edge cases such as an empty tree, where we would return None or raise an exception. If the target value is equal to a node's value, we should immediately return that value since it is the closest.

Find the Closest Value in a Binary Search Tree

Coupang

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Coupang Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string