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

Example

``````Input
type: post
-----
Binary Search Tree:
9
/   \
4      17
/ \      \
3   6      22
/ \     /
5   7   20

target: 18

Output
type: post
------
17``````

### METHOD 1. Recursive solution

Complexity

• Average: O(log(n)) time | O(log(n)) space
• Worst: O(n) time | O(n) space
``````class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}

class ClosestElementInBST {
private static TreeNode findClosestNode(TreeNode node, int target) {
if (target < node.val && node.left != null) {
// Closest node is either the current node or a node in the left subtree
TreeNode closestNodeLeftSubtree = findClosestNode(node.left, target);
return getClosestNode(node, closestNodeLeftSubtree, target);
} else if (target > node.val && node.right != null){
// Closest node is either the current node or a node in the right subtree
TreeNode closestNodeRightSubtree = findClosestNode(node.right, target);
return getClosestNode(node, closestNodeRightSubtree, target);
} else {
return node;
}
}

private static TreeNode getClosestNode(TreeNode node1, TreeNode node2, int target) {
if(Math.abs(target - node1.val) < Math.abs(target - node2.val)) {
return node1;
} else {
return node2;
}
}

public static void main(String[] args) {
TreeNode node = new TreeNode(9);
node.left = new TreeNode(4);
node.right = new TreeNode(17);

node.left.left = new TreeNode(3);
node.left.right = new TreeNode(6);
node.left.right.left = new TreeNode(5);
node.left.right.right = new TreeNode(7);

node.right.right = new TreeNode(22);
node.right.right.left = new TreeNode(20);

TreeNode closestNode = findClosestNode(node, 18)
System.out.println(closestNode.val);
}
}``````

### METHOD 2. Iterative solution

Complexity

• Average: O(log(n)) time | O(1) space
• Worst: O(n) time | O(1) space
``````class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}

class ClosestElementInBST {

private static int findClosestValue(TreeNode node, int target) {
TreeNode currentNode = node;
int closestValue = currentNode.val;
double minDiff = Double.MAX_VALUE;

while(currentNode != null) {
double currentDiff = Math.abs(target - currentNode.val);
if(currentDiff < minDiff) {
minDiff = currentDiff;
closestValue = currentNode.val;
}
if(target < currentNode.val) {
currentNode = currentNode.left;
} else if (target > currentNode.val) {
currentNode = currentNode.right;
} else {
break;
}
}
return closestValue;
}

public static void main(String[] args) {
TreeNode node = new TreeNode(9);
node.left = new TreeNode(4);
node.right = new TreeNode(17);

node.left.left = new TreeNode(3);
node.left.right = new TreeNode(6);
node.left.right.left = new TreeNode(5);
node.left.right.right = new TreeNode(7);

node.right.right = new TreeNode(22);
node.right.right.left = new TreeNode(20);

System.out.println(findClosestValue(node, 18));
}
}``````