Find Closest Value in BST

To solve finding the closest value in a Binary Search Tree efficiently, I would first clarify that we are looking for the node whose value has the smallest absolute difference from the target. Since this is a BST, I know that all values in the left subtree are smaller than the root, and all in the right are larger. A naive approach would visit every node, taking O(N) time, but we can do much better. My strategy uses the BST property to prune the search space. I will maintain a variable for the closest value found so far, initialized to the root. Starting at the root, I compare the current node's value with the target. If they match exactly, I return immediately. If the target is smaller, I know the closest value must be in the left subtree or the current node itself, so I move left. Conversely, if the target is larger, I move right. Crucially, at every step before moving, I update my closest value if the current node is closer to the target than what I've seen. For example, if the tree has a root of 5 and I'm looking for 4.9, I check 5. The difference is 0.1. Since 4.9 is less than 5, I go left. If the next node is 2, the difference is 2.9, which is worse, so I keep 5. Since 4.9 is greater than 2, I go right. This continues until I hit a leaf. This ensures an O(H) time complexity, which is optimal for balanced trees, aligning with Meta's focus on scalable, efficient algorithms.