Closest Nodes Queries In A Binary Search Tree - Leetcode Solution

Problem statement: Given a binary search tree (BST) and a target node k, find the two closest nodes to k in the BST.

Solution: We can solve this problem using iterative or recursive approach. However, in this solution, I will explain the iterative approach.

We will traverse the BST in inorder and maintain a queue of size 2 with the closest nodes seen so far. Let's call this queue closestNodes.

Algorithm:

1. Initialize a variable curr to the root of the BST.
2. Initialize an empty queue closestNodes.
3. While curr is not null or closestNodes is not empty: a. If curr is not null, push curr onto a stack and update curr to its left child. b. If curr is null, pop an element node from the stack and: i. If closestNodes is empty, push node onto closestNodes. ii. If node is closer to the target than the first element in closestNodes, insert node at the front of closestNodes. iii. Else if node is closer to the target than the second element in closestNodes, insert node at the second position in closestNodes. iv. If the size of closestNodes is greater than 2, remove the last element from closestNodes. v. Update curr to node's right child.
4. Return the two elements in closestNodes.

Let's analyze the time and space complexity of this algorithm. Time complexity is O(h+k), where h is the height of the BST and k is the number of closest nodes we want to find. Space complexity depends on the size of the stack used for inorder traversal and is O(h).

Here's the implementation of the above algorithm:

public List<Integer> closestNodes(TreeNode root, double target) {
    Stack<TreeNode> stack = new Stack<>();
    List<Integer> closestNodes = new ArrayList<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        TreeNode node = stack.pop();
        if (closestNodes.isEmpty()) {
            closestNodes.add(node.val);
        } else if (Math.abs(node.val - target) < Math.abs(closestNodes.get(0) - target)) {
            closestNodes.add(0, node.val);
        } else if (closestNodes.size() < 2 || Math.abs(node.val - target) < Math.abs(closestNodes.get(1) - target)) {
            closestNodes.add(1, node.val);
        }
        if (closestNodes.size() > 2) {
            closestNodes.remove(2);
        }
        curr = node.right;
    }
    return closestNodes;
}

Note: This solution assumes that the input BST does not have any duplicates. If duplicates exist, we need to modify the condition on lines 10-12 to ensure that we don't add the same value to closestNodes.

1