LeetCode 270: Closest Binary Search Tree Value

Explanation:

To find the closest value in a binary search tree (BST) to a given target value, we can perform an in-order traversal of the BST. During the traversal, we keep track of the node whose value is closest to the target value.

1. Start with the root of the BST.
2. While traversing the BST:
   • If the current node's value is closer to the target than the previously closest node's value, update the closest node.
   • Move to the left or right child based on the value comparison with the target.
3. Return the value of the closest node found.

Time Complexity:
The time complexity of this approach is O(logN) on average, where N is the number of nodes in the BST. In the worst case, it can be O(N) for skewed trees.

Space Complexity:
The space complexity is O(1) as we are not using any additional data structures.

:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int closestValue(TreeNode root, double target) {
        int closest = root.val;
        
        while (root != null) {
            closest = Math.abs(root.val - target) < Math.abs(closest - target) ? root.val : closest;
            root = target < root.val ? root.left : root.right;
        }
        
        return closest;
    }
}