Question

Formatted question description: https://leetcode.ca/all/272.html

 272	Closest Binary Search Tree Value II

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

 Example:

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

    4
   / \
  2   5
 / \
1   3

 Output: [4,3]

 Note:

 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.

 Follow up:
 Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

 Hint:

 1. Consider implement these two helper functions:
 　　i. getPredecessor(N), which returns the next smaller node to N.
 　　ii. getSuccessor(N), which returns the next larger node to N.
 2. Try to assume that each node has a parent pointer, it makes the problem much easier.
 3. Without parent pointer we just need to keep track of the path from the root to the current node using a stack.
 4. You would need two stacks to track the path in finding predecessor and successor node separately.

 @tag-tree

Algorithm

This tree is considered balanced if: the difference between heights of the left subtree and right subtree is not more than 1.

In-order

The comparison is completed during the in-order traversal.

When traversing to a node,

If the result array is less than k at this time, add this node value directly to the result,
If the absolute value of the difference between the node value and the target value is less than the absolute value of the difference between the first element of the result and the target value, indicating that the current value is closer to the target value, delete the first element and add the current node value to the end,
On the contrary, it means that the current value deviates more from the target value than all the values in the result res. Due to the characteristics of the in-order traversal, the subsequent values will deviate further, so the final result is directly returned at this time

Heap

A pair of difference diff and node value stored in the heap.

In order to traverse the binary tree (other traversal methods can also be used), and then calculate the absolute value of the difference between the target value and the target value for each node value.

Due to the nature of the maximum heap, the largest diff is automatically the first to maintain k pairs, if If there are more than k, delete the big pair at the front of the heap, and remove the node value in the pair for the k pairs left and store it in the result.

Code

import java.util.LinkedList;
import java.util.List;

public class Closest_Binary_Search_Tree_Value_II {

    public static void main(String[] args) {
        Closest_Binary_Search_Tree_Value_II out = new Closest_Binary_Search_Tree_Value_II();
        Solution s = out.new Solution();

        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);

        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);

        System.out.println(s.closestKValues(root, 3.714286, 2));
    }

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */


    public class Solution {

        LinkedList<Integer> result = new LinkedList<>();

        public List<Integer> closestKValues(TreeNode root, double target, int k) {
            inOrderTraversal(root, target, k);
            return result;
        }

        private void inOrderTraversal(TreeNode root, double target, int k) {
            if (root == null) {
                return;
            }
            inOrderTraversal(root.left, target, k);
            if (result.size() < k) {
                result.add(root.val);
            } else if(result.size() == k) { // hand-made priority queue
                if (Math.abs(result.getFirst() - target) > (Math.abs(root.val - target))) {
                    result.removeFirst();
                    result.addLast(root.val);
                } else { // meaning, current node value is further than both first and last value of result list
                    return; // diff is larger, so skip, as trim
                }
            }
            inOrderTraversal(root.right, target, k);
        }
    }
}

############

/**
 * 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 {
    private List<Integer> ans;
    private double target;
    private int k;

    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        ans = new LinkedList<>();
        this.target = target;
        this.k = k;
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (ans.size() < k) {
            ans.add(root.val);
        } else {
            if (Math.abs(root.val - target) >= Math.abs(ans.get(0) - target)) {
                return;
            }
            ans.remove(0);
            ans.add(root.val);
        }
        dfs(root.right);
    }
}

// solution with heap and diff
class Solution {
public:
    vector<int> closestKValues(TreeNode* root, double target, int k) {
        vector<int> res;
        priority_queue<pair<double, int>> q;
        inorder(root, target, k, q);
        while (!q.empty()) {
            res.push_back(q.top().second);
            q.pop();
        }
        return res;
    }
    void inorder(TreeNode *root, double target, int k, priority_queue<pair<double, int>> &q) {
        if (!root) return;
        inorder(root->left, target, k, q);
        q.push({abs(root->val - target), root->val});
        if (q.size() > k) q.pop();
        inorder(root->right, target, k, q);
    }
};

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]:
        def dfs(root):
            if root is None:
                return
            dfs(root.left)
            if len(q) < k:
                q.append(root.val)
            else:
                if abs(root.val - target) >= abs(q[0] - target):
                    return # trim: meaning, current node value is further than both first and last value of result list
                q.popleft()
                q.append(root.val)
            dfs(root.right)

        q = deque()
        dfs(root)
        return list(q)

############

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
  def closestKValues(self, root, target, k):
    """
    :type root: TreeNode
    :type target: float
    :type k: int
    :rtype: List[int]
    """
    ans = []
    preStack = []
    sucStack = []

    while root:
      if root.val < target:
        preStack.append(root)
        root = root.right
      else:
        sucStack.append(root)
        root = root.left

    def getPredecessor(stack):
      if not stack:
        return
      pre = stack.pop()
      p = pre.left
      while p:
        stack.append(p)
        p = p.right
      return pre

    def getSuccessor(stack):
      if not stack:
        return
      suc = stack.pop()
      p = suc.right
      while p:
        stack.append(p)
        p = p.left
      return suc

    pre = getPredecessor(preStack)
    suc = getSuccessor(sucStack)

    while k:
      k -= 1
      if pre and not suc:
        ans.append(pre.val)
        pre = getPredecessor(preStack)
      elif not pre and suc:
        ans.append(suc.val)
        suc = getSuccessor(sucStack)
      elif pre and suc and abs(pre.val - target) <= abs(suc.val - target):
        ans.append(pre.val)
        pre = getPredecessor(preStack)
      elif pre and suc and abs(pre.val - target) >= abs(suc.val - target):
        ans.append(suc.val)
        suc = getSuccessor(sucStack)
    return ans

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func closestKValues(root *TreeNode, target float64, k int) []int {
	var ans []int
	var dfs func(root *TreeNode)
	dfs = func(root *TreeNode) {
		if root == nil {
			return
		}
		dfs(root.Left)
		if len(ans) < k {
			ans = append(ans, root.Val)
		} else {
			if math.Abs(float64(root.Val)-target) >= math.Abs(float64(ans[0])-target) {
				return
			}
			ans = ans[1:]
			ans = append(ans, root.Val)
		}
		dfs(root.Right)
	}
	dfs(root)
	return ans
}

272 - Closest Binary Search Tree Value II

Question

Algorithm

In-order

Heap

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

In-order

Heap

Code

All Problems

All Solutions