Find the Stored Value Nearest to a Number
Solve this ProblemYou are given the root of a binary search tree with distinct values and an integer target. Return the value in the tree that is closest to target — the one with the smallest absolute difference. If two values are equally close, return the smaller one. If the tree is empty, return -1.
Comparing against every value works. Since the nearest value must lie along the search path for the target, one walk from the root is enough.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000 - ◆
The tree is a binary search tree (left subtree smaller, right subtree larger at every node), given by its root node - ◆
0 ≤ target ≤ 1000 (an integer that need not be in the tree) - ◆
Return the tree value whose distance |value − target| is smallest. If two values are equally close, return the smaller one. An empty tree gives -1
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — List All Values, Compare Every Distance
BruteCollect all values with an inorder walk (they come out ascending), then scan them keeping the value whose distance to the target is smallest so far. Because the list is ascending and the update needs a STRICTLY smaller distance, on a tie the earlier — smaller — value is kept, which is exactly the required tie rule. It works but always visits all n nodes and stores them: O(n) time, O(n) space.
O(n)O(n)1class Solution {
2 public int closestValue(TreeNode root, int target) {
3 List<Integer> vals = new ArrayList<>();
4 inorder(root, vals);
5 if (vals.isEmpty()) return -1;
6 int best = vals.get(0);
7 for (int v : vals) {
8 if (Math.abs(v - target) < Math.abs(best - target)) best = v;
9 }
10 return best;
11 }
12
13 private void inorder(TreeNode node, List<Integer> vals) {
14 if (node == null) return;
15 inorder(node.left, vals);
16 vals.add(node.val);
17 inorder(node.right, vals);
18 }
19}Optimal — Follow the Search Path Toward the Target
OptimalThe nearest value must lie on the path you would follow when searching for the target: at each node, the values that could be nearer than the current node are only on the side the target points to. So walk that path — compare each visited node's distance with the best so far, replacing it when the distance is smaller, or equal with a smaller value — and stop early if the target itself is found. Only one root-to-leaf path is visited: O(h) time and O(1) space.
O(h)O(1)1class Solution {
2 public int closestValue(TreeNode root, int target) {
3 if (root == null) return -1;
4 int best = root.val;
5 TreeNode cur = root;
6 while (cur != null) {
7 int d = Math.abs(cur.val - target);
8 int bestD = Math.abs(best - target);
9 if (d < bestD || (d == bestD && cur.val < best)) best = cur.val;
10 if (cur.val == target) break;
11 cur = target < cur.val ? cur.left : cur.right;
12 }
13 return best;
14 }
15}