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.

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

Solution

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) {
        Deque<Integer> res = new LinkedList<>();

        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);
                }
                res.add(current.val);
                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.