30. Closest Neighbour in BST
β GFG solution to the Closest Neighbour in BST problem: find the greatest value β€ k using BST properties. π
The problem can be found at the following link: π Question Link
π§© Problem Description
Given the root of a Binary Search Tree and a value k
, find the greatest node value in the tree that is less than or equal to k
. If no such node exists, return -1
.
π Examples
Example 1
Input: root = [10,7,15,2,8,11,16], k = 14
Output: 11
Explanation: The greatest element β€ 14 is 11.
Example 2
Input: root = [5,2,12,1,3,9,21,null,null,null,null,null,null,19,25], k = 24
Output: 21
Explanation: The greatest element β€ 24 is 21.
Example 3
Input: root = [5,2,12,1,3,9,21,null,null,null,null,null,null,19,25], k = 4
Output: 3
Explanation: The greatest element β€ 4 is 3.
π Constraints
Number of nodes (N): $(1 \le N \le 10^5)$
Node values and (k): $(1 \le \text{data}, k \le 10^5)$
All node values are unique
β
My Approach
Iterative BST Floor Search
Idea:
Leverage BST property: left subtree < node < right subtree.
Keep a variable
res = -1
.Start at the root and traverse:
If
node->data == k
, it's the best possible floor β returnk
.If
node->data < k
, recordres = node->data
and move right to look for a closer larger value β€ k.If
node->data > k
, move left to find smaller values.
Why It Works:
Each step eliminates half of the tree, guaranteeing we never miss a closer candidate.
Answer:
After the loop,
res
holds the greatest value β€ k, or-1
if none found.
π Expected Time and Auxiliary Space Complexity
Expected Time Complexity: O(H), where H = height of the tree, since we traverse at most one path down the BST.
Expected Auxiliary Space Complexity: O(1), as only a few variables are used.
π§βπ» Code (C++)
class Solution {
public:
int findMaxFork(Node* root, int k) {
int res = -1;
while (root) {
if (root->data == k) return k;
if (root->data < k) {
res = root->data;
root = root->right;
} else {
root = root->left;
}
}
return res;
}
};
π§βπ» Code (Java)
class Solution {
public int findMaxFork(Node root, int k) {
int res = -1;
while (root != null) {
if (root.data == k) return k;
if (root.data < k) {
res = root.data;
root = root.right;
} else {
root = root.left;
}
}
return res;
}
}
π Code (Python)
class Solution:
def findMaxFork(self, root, k):
res = -1
while root:
if root.data == k:
return k
if root.data < k:
res = root.data
root = root.right
else:
root = root.left
return res
π§ Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: π¬ Any Questions?. Letβs make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
πVisitor Count
Last updated