# Binary Search Tree Value II

This page explains Java solution to problem `Binary Search Tree Value II` using Inorder traversal of `Binary Search tree` data structure.

## Problem Statement

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

• Given target value is a floating point.
• You may assume `k` is always valid, that is: `k ≤ total` nodes.
• You are guaranteed to have only one unique set of `k` values in the BST that are closest to the target.
Example 1:

Input: root = [4,2,5,1,3], target = 3.714286, and k = 2
Output: [4,3]

## Solution

If you have any suggestions in below code, please create a pull request by clicking here.
``````
package com.vc.hard;

import java.util.*;

/**
* 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 ClosestBinarySearchTreeValueIi {
public List<Integer> closestKValues(TreeNode root, double target, int k) {

TreeNode current = root;
Stack<TreeNode> st = new Stack<>();
while(current != null || !st.isEmpty()) {
if(current != null) {
st.push(current);
current = current.left;
}
else {
current = st.pop();
if(res.size() == k) {
double diff = Math.abs(target - res.peekFirst());
double currentDiff = Math.abs(target - current.val);
if(currentDiff < diff) res.pollFirst();
else return new ArrayList<>(res);
}
current = current.right;
}
}
return new ArrayList<>(res);
}
}
``````

## Time Complexity

O(N) Where
N is total number of nodes in an input tree.

## Space Complexity

O(K) Where
K is total number of closest value to return.