Closest in BST

Problem Overview

In a BST, every left child is smaller than its parent and every right child is larger.

Intuition

In a BST, every left child is smaller than its parent and every right child is larger. That order points to the only subtree that can hold a closer value to k. Starting at the root, the absolute difference to k is recorded, then the walk moves left when k is smaller than the node and right otherwise. Each step can only improve or keep the closest difference found so far. When a node equals k the difference is 0 and the search stops. Because only one child is chosen at every node, the walk follows a single root-to-leaf path and never needs a full tree scan.

Algorithm

1Start at the root with the closest difference set to a large sentinel.
2While the current node exists, update the closest difference with the absolute gap between the node value and k.
3Return 0 immediately when that gap is 0.
4Move to the left child when k is smaller than the node value, otherwise move to the right child.
5Return the closest difference after the path ends.

Example Walkthrough

Input: root = [10, 2, 11, 1, 5, N, N, N, N, 3, 6], k = 13

1. At 10 the gap is 3. Because 13 is larger, the walk moves right to 11.
2. At 11 the gap is 2, which is better, and the right child is empty.
3. No closer node remains on that path, so the answer is 2.

Output: 2

Common Pitfalls

• Use the BST order. Visiting every node works but is slower than a single path walk.
• An exact match should return 0 at once. Continuing the walk cannot improve on zero.
• Compare with absolute difference. The closest node may be larger or smaller than k.
• The iterative walk uses constant extra space. A recursive version spends stack space equal to the height.

Closest in BST.java

Java

// Approach: Walk one root-to-leaf path using the BST order. At each node,
// update the closest absolute difference to k, then go left when k is
// smaller and right otherwise. An exact match returns 0 at once. Only one
// path is visited, so the bound is already tight for a BST search.
// Complexity: O(h) time, O(1) extra space, where h is the tree height.

class Node {
    int data;
    Node left, right;

    public Node(int val) {
        data = val;
        left = right = null;
    }
}

class Solution {
    public int minDiff(Node root, int k) {
        int ans = Integer.MAX_VALUE;

        while (root != null) {
            ans = Math.min(ans, Math.abs(root.data - k));
            if (ans == 0) {
                return 0;
            }
            root = k < root.data ? root.left : root.right;
        }
        return ans;
    }
}

Was this solution helpful?