Closest Binary Search Tree Value

Closest Binary Search Tree Value

What is this problem about?

In the Closest Binary Search Tree Value interview question, you are given a Binary Search Tree (BST) and a target floating-point value. Your task is to find the value in the BST that is closest to the given target. Because it's a BST, you can leverage the sorted property of the nodes to find the answer much faster than a linear search through all nodes.

Why is this asked in interviews?

This is a classic Binary Search Tree interview pattern used by companies like Microsoft and Meta. It tests your ability to navigate a BST and your understanding of how to prune search paths. It’s an "Easy" difficulty problem that quickly reveals if a candidate understands the fundamental property of BSTs: for any node, values in the left subtree are smaller and values in the right subtree are larger.

Algorithmic pattern used

The core pattern is Binary Search applied to a tree. Instead of checking every node, you compare the target with the current node's value. If the target is smaller than the current value, the "closest" value could be the current node or something in the left subtree. If the target is larger, it could be the current node or something in the right subtree.

Example explanation

Target: 3.7 Tree: 5 / 2 8 / 1 4

1. Start at 5. Difference is |5 - 3.7| = 1.3. Current closest is 5.
2. 3.7 < 5, so move to the left child 2.
3. Difference is |2 - 3.7| = 1.7. 1.3 is smaller, so 5 remains closest.
4. 3.7 > 2, so move to the right child 4.
5. Difference is |4 - 3.7| = 0.3. 0.3 is smaller than 1.3, so 4 becomes the new closest.
6. 4 has no children. Return 4.

Common mistakes candidates make

• Initial Closest Value: Not initializing the "closest" variable correctly (e.g., initializing to 0 when all tree values are large).
• Rounding Errors: Forgetting that the target is a float and the node values are integers.
• Inefficient Search: Traversal of the entire tree (O(N)) instead of leveraging the BST property (O(log N)).

Interview preparation tip

Remember that in a BST, you only ever need to go down one path from the root to a leaf. This means the time complexity should be proportional to the height of the tree.