Leetcode 272. Closest Binary Search Tree Value II

Problem Explanation:

We are given a Binary Search Tree (BST), a target value, and a count (k). We have to return the k nodes/values present in the BST which are closest to the target value.

Algorithm

The algorithm is based on the depth-first search (DFS).

Firstly, we pass through each node and store the values in a queue. To obtain the inorder traversal of the tree, the function is called recursively to traverse the left side, then store the current node's value, and finally traverse the right side.

Next, we traverse the queue until it contains k elements. We compare the first and last elements of the queue with the target. If the difference with the target is more for either first or last element, we remove that element from the queue.

Example: Let's consider an example where the tree is

1
2text
3       4
4     /   \
5    2     5
6  /   \
7 1     3

If the target is 3.7 and k is 2, after implementing the inorder traversal the queue becomes [1, 2, 3, 4, 5]. From this queue we have to find the 2 closest elements to the target which are 3 and 4. So, the function would return [3, 4].

Python Solution:

1
2python
3class Solution:
4    def closestKValues(self, root: TreeNode, target: float, k: int) -> List[int]<=k<=n:
5        q=[]
6#obtain in-order traversal of the tree to get an ordered queue
7        def inorder(root):
8            if root is None : return
9            inorder(root.left)
10            q.append(root.val)
11            inorder(root.right)
12            
13        inorder(root)
14#until our queue returns k closest elements from target   
15        while len(q)>k:
16            if abs(q[0]-target)>abs(q[-1]-target):
17                q.pop(0)
18            else:
19                q.pop()
20                 
21        return q

C++ Solution:

1
2c++
3class Solution {
4public:
5    vector<int> closestKValues(TreeNode* root, double target, int k) {
6        deque<int> q;
7        self::inOrder(root,q);
8        while(q.size()>k){
9            if(abs(q.front()-target)>abs(q.back()-target)) q.pop_front();
10            else q.pop_back();
11        }
12        return {q.begin(), q.end()};;
13    }
14    void inOrder(TreeNode* root, deque<int>& q){
15        if(root==NULL) return;
16        inOrder(root->left, q);
17        q.push_back(root->val);
18        inOrder(root->right, q);
19    }
20};

Java Solution:

1
2java
3class Solution {
4    class Node {
5        int val ;
6        double diff ;
7        public Node(int val, double diff) {
8            this.val = val;
9            this.diff = diff;
10        }
11    }
12    public List<Integer> closestKValues(TreeNode root, double target, int k) {
13        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
14            public int compare(Node a, Node b) {
15                if(a.diff > b.diff) {
16                    return -1;
17                }else if(a.diff < b.diff) {
18                    return 1;
19                }else {
20                    return 0;
21                }
22            }
23        });
24        
25        traverse(root, target, k, pq);
26        List<Integer> res = new ArrayList<>();
27        while(!pq.isEmpty()) {
28            res.add(0, pq.poll().val);
29        }
30        return res;
31    }
32    private void traverse(TreeNode root, double target, int k, PriorityQueue<Node> pq) {
33        if(root == null) {
34            return;
35        }
36        traverse(root.left, target, k, pq);
37        pq.offer(new Node(root.val, Math.abs(root.val - target)));
38        if(pq.size() > k) {
39            pq.poll();
40        }
41        traverse(root.right, target, k, pq);
42    }
43}

JavaScript Solution:

1
2javascript
3class BSTNode {
4    constructor(val) {
5        this.val = val;
6        this.left = null;
7        this.right = null;
8    }
9}
10
11function closestKValues(root, target, k) {
12    let result = [];
13    inorderTraversal(root);
14    while (result.length > k) {
15        if (Math.abs(result[0] - target) > Math.abs(result[result.length - 1] - target)) {
16            result.shift();
17        } else {
18            result.pop();
19        }
20    }
21    return result;
22
23    function inorderTraversal(root) {
24        if (!root) return;
25        inorderTraversal(root.left);
26        result.push(root.val);
27        inorderTraversal(root.right);
28    }
29}
30
31// creating BST
32let root = new BSTNode(4);
33root.left = new BSTNode(2);
34root.right = new BSTNode(5);
35root.left.left = new BSTNode(1);
36root.left.right = new BSTNode(3);
37console.log(closestKValues(root, 3.7, 2)); // output: [3, 4]

In JavaScript, we defined a class BSTNode to create a Binary Search Tree. Then in closestKValues(), We've created a queue using the inOrderTraversal(), which contains the elements from BST in sorted order. Then we remove maximum or minimum side elements from the queue based on the difference between the first/last element and target. We continue such operations until we have only k elements in the queue. In the end, the queue contains the closest k elements.

Conclusion

We have provided a solution to the problem in multiple programming languages. In binary search trees, an inorder traversal returns nodes in ascending order and it is a significant property used in these solutions. The main crux of these solutions lies in how we manipulate the queue to achieve the required number of closest elements.

Important points to note:

• In the Python and JavaScript solutions, we remove elements from the front or back of the queue based on whether the first or last element is farther from the target.
• In the Java solution, we use a max heap to keep track of the closest k values. The heap is updated while doing the inorder traversal of the tree.

Each of these solutions varies slightly based on the characteristics of the languages, but the underlying algorithm remains the same.