Closest Binary Search Tree Value - Video Solutions

Problem Overview: Given the root of a Binary Search Tree and a floating-point target value, return the node value in the tree that is numerically closest to the target. The key advantage comes from the BST ordering property, which lets you eliminate half of the tree at each step.

Approach 1: Recursive BST Traversal (O(h) time, O(h) space)

This method performs a depth-first search while leveraging the Binary Search Tree property: left subtree values are smaller and right subtree values are larger than the current node. Maintain a variable closest that stores the value with the smallest absolute difference from the target. At each node, compare abs(node.val - target) with the current best and update if necessary. Then choose the next subtree: move left if target < node.val, otherwise move right. Because you only follow one branch at each step, the traversal behaves like binary search on the tree. Time complexity is O(h), where h is the tree height, and space complexity is O(h) due to the recursion stack. This approach fits naturally when implementing recursive depth-first search on a binary search tree.

Approach 2: Iterative Binary Search on BST (O(h) time, O(1) space)

The iterative version follows the exact same logic but avoids recursion. Start from the root and track the current best candidate in a variable closest. For each node, update the candidate if the absolute difference with the target is smaller than the previous best. Then move to either the left or right child depending on the BST ordering rule. Because only one path from root to leaf is explored, the traversal resembles classic binary search. The time complexity remains O(h), which is O(log n) for balanced trees and O(n) in the worst case of a skewed tree. Space complexity improves to O(1) since no recursion stack is used.

Recommended for interviews: Interviewers expect you to recognize and exploit the Binary Search Tree property. A naive full traversal would take O(n), but using the BST ordering reduces the search to O(h). Start by explaining that you keep track of the closest value while traversing the path determined by the target. The iterative solution is usually preferred because it avoids recursion overhead and demonstrates clear understanding of BST-based binary search.