LeetCode 270 – Closest Binary Search Tree Value

This question has been asked a lot by meta recently.
You can solve this question either by using a simple inorder traversal, which will take O(n) time and O(n) space complexity, or you can use the property of binary search and solve this in O(logn) time complexity and O(logn) space complexity due to the nature of the Binary Search Tree that values to the left of the node are always smaller than to the right.

Let’s take a look at the inorder traversal solution.

class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        

        self.closest = float("inf")
        def dfs(node):
            if not node:
                return 

            dfs(node.left)

            if abs(self.closest - target) > abs(node.val - target):
                self.closest = node.val

            if abs(self.closest - target) == abs(node.val - target):
                self.closest = min(node.val, self.closest)

            dfs(node.right)

        dfs(root)
        return self.closest

Here, we begin by creating a variable called closest. We then perform an inorder traversal of the binary search tree, evaluating whether the value of the current node is the closest to our target value. If we find that it is indeed closer, we update our closest variable accordingly. Additionally, we compare it with our previous estimate of closest. If they are equal, we then set our closest variable to the minimum of the two values, as specified in the problem statement.

Although this initial approach leads to a solution that is acceptable, it has a time complexity of O(n) and a space complexity of O(n). However, we can enhance our efficiency by halving our search space with each decision. In the worst-case scenario—where the tree is unbalanced from the root to the leaf—this method will still operate at O(n) time complexity. On average, though, we achieve a more efficient solution with a time complexity of O(log N).

By leveraging the properties of binary search trees, we ensure a more optimized search strategy. This not only improves performance but also ensures that our solution scales better with larger datasets.

class Solution:
    def closestValue(self, root: Optional[TreeNode], target: float) -> int:
        self.closest = float("inf")
        def dfs(node):
            if not node:
                return

            if abs(self.closest - target) > abs(node.val - target):
                self.closest = node.val

            if abs(self.closest - target) == abs(node.val - target):
                self.closest = min(node.val, self.closest)

            if target < node.val:
                dfs(node.left)
            else:
                dfs(node.right)

        dfs(root)
        return self.closest

Here, we reinitialize our variable closest. Instead of performing an inorder traversal, we check if the value of the current node is closer to the target. We then determine whether the target value is less than the value of the current node. If it is, we conduct a Depth-First Search (DFS) only on the left side of the tree; otherwise, we proceed with a DFS on the right side.

This approach effectively halves our search space, allowing us to achieve a time complexity of O(log N).