Closest Neighbour in BST

JavaView on GFG

Time: O(h)

Space: O(1)

Intuition

Find value in BST closest to a given target. BST traversal updating minimum difference.

Algorithm

1Traverse BST. Update closest when |node.val - target| < current min diff. Go left if target < node, else right.

Common Pitfalls

•BST property guides traversal. Track closest seen so far. O(h) time where h = tree height.

Closest Neighbour in BST.java

Java

// Approach: BST traversal. At each node, update the closest value seen so far and move left or right.
// Time: O(h) Space: O(1)
class Solution {
    public int findMaxFork(Node root, int k) {
        int ans = -1;

        while (root != null) {
            if (root.data == k)
                return k;
            else if (root.data < k) {
                ans = root.data;
                root = root.right;
            } else
                root = root.left;
        }

        return ans;
    }
}

Was this solution helpful?