Find the Closest Element in Binary Search Tree - Java Solution

1. Introduction

In this blog post, we'll solve a common problem in binary search trees (BSTs) - finding the value in the BST that is closest to a given target value. This problem is a great exercise in understanding the properties of BSTs and how to efficiently traverse them.

Problem

Given a non-empty binary search tree and a target value, the task is to find the value in the BST that is closest to the target.

2. Solution Steps

1. Start by initializing a variable to keep track of the closest value found so far.

2. Traverse the BST starting from the root. At each node, update the closest value if the current node's value is closer to the target than the previously recorded closest value.

3. Depending on the target value and the current node's value, move to the left or right child of the current node.

4. Continue this process until all nodes have been examined.

5. Return the closest value found.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        TreeNode root = new TreeNode(9);
        root.left = new TreeNode(4);
        root.right = new TreeNode(17);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(6);
        root.left.right.left = new TreeNode(5);
        root.left.right.right = new TreeNode(7);
        root.right.right = new TreeNode(22);
        root.right.right.left = new TreeNode(20);

        int target = 12;
        System.out.println("Closest value to " + target + " is: " + closestValue(root, target));
    }

    // Method to find the value in the BST that is closest to the target
    public static int closestValue(TreeNode root, int target) {
        int closest = root.val; // Initialize closest value

        TreeNode current = root;
        while (current != null) {
            // Update closest value if the current value is closer to the target
            if (Math.abs(target - current.val) < Math.abs(target - closest)) {
                closest = current.val;
            }

            // Move to the left or right child
            if (target < current.val) {
                current = current.left;
            } else {
                current = current.right;
            }
        }

        return closest; // Return the closest value found
    }
}

Output:

Closest value to 12 is: 9

Explanation:

In the given BST, the value that is closest to the target value 12 is 9. 

The closestValue method traverses the tree, starting from the root. At each step, it checks if the current node's value is closer to the target than the previously recorded closest value. It then moves left or right depending on how the current node's value compares to the target, leading to an efficient search for the closest value.