123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103
#include <bits/stdc++.h>
using namespace std;
// Definition for a binary tree node.
class TreeNode {
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
vector<int> floorCeilOfBST(TreeNode* root, int key) {
// Initialize the floor and ceil values
int floor = -1;
int ceil = -1;
// Find the floor value
// Start from the root of the BST
TreeNode* current = root;
while (current) {
// If the key matches the current node's value
if (current->data == key) {
// Set floor to this value
floor = current->data;
break;
/* If the key is greater than the current node's value
Update floor to the current node's value
If the key is smaller than the current node's value
Move to the left subtree to find a smaller value */
} else if (current->data < key) {
floor = current->data;
current = current->right;
} else {
current = current->left;
}
}
// Find the ceil value
// Reset current to start from the root again
current = root;
while (current) {
// If the key matches the current node's value
if (current->data == key) {
// Set ceil to this value
ceil = current->data;
break;
/* If the key is smaller than the current node's value
Update ceil to the current node's value
If the key is greater than the current node's value
Move to the right subtree to find a larger value */
} else if (current->data > key) {
ceil = current->data;
current = current->left;
} else {
current = current->right;
}
}
// Return the floor and ceil values as a vector
return {floor, ceil};
}
};
// Utility function to insert a new node with given key in BST
TreeNode* insert(TreeNode* node, int key) {
if (node == nullptr) return new TreeNode(key);
if (key < node->data)
node->left = insert(node->left, key);
else if (key > node->data)
node->right = insert(node->right, key);
return node;
}
int main() {
// Create the BST
TreeNode* root = nullptr;
root = insert(root, 8);
insert(root, 4);
insert(root, 12);
insert(root, 2);
insert(root, 6);
insert(root, 10);
insert(root, 14);
// Key value to find floor and ceil for
int key = 11;
// Solution instance
Solution sol;
vector<int> result = sol.floorCeilOfBST(root, key);
// Output the floor and ceil values
cout << "Floor: " << result[0] << ", Ceil: " << result[1] << endl;
return 0;
}
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485
import java.util.*;
class TreeNode {
int data;
TreeNode left, right;
TreeNode(int val) {
data = val;
left = right = null;
}
}
class Solution {
public List<Integer> floorCeilOfBST(TreeNode root, int key) {
// Initialize floor and ceil values to -1, indicating not found
int floor = -1;
int ceil = -1;
// Find the floor value
// Start from the root of the BST
TreeNode current = root;
while (current != null) {
// If the key matches the current node's value
if (current.data == key) {
// Set floor to this value
floor = current.data;
break;
/* If the key is greater than the current node's value
Update floor to the current node's value
If the key is smaller than the current node's value
Move to the left subtree to find a smaller value */
} else if (current.data < key) {
floor = current.data;
current = current.right;
} else {
current = current.left;
}
}
// Find the ceil value
// Reset current to start from the root again
current = root;
while (current != null) {
// If the key matches the current node's value
if (current.data == key) {
// Set ceil to this value
ceil = current.data;
break;
/* If the key is smaller than the current node's value
Update ceil to the current node's value
If the key is greater than the current node's value
Move to the right subtree to find a larger value */
} else if (current.data > key) {
ceil = current.data;
current = current.left;
} else {
current = current.right;
}
}
// Return floor and ceil values as a list
return Arrays.asList(floor, ceil);
}
public static void main(String[] args) {
// Creating a sample BST
TreeNode root = new TreeNode(8);
root.left = new TreeNode(4);
root.right = new TreeNode(12);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(6);
root.right.left = new TreeNode(10);
root.right.right = new TreeNode(14);
Solution sol = new Solution();
int key = 11; // Key to find floor and ceil for
// Find and print floor and ceil values
List<Integer> result = sol.floorCeilOfBST(root, key);
System.out.println("Floor: " + result.get(0) + ", Ceil: " + result.get(1));
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374
# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.data = val
self.left = left
self.right = right
class Solution:
def floorCeilOfBST(self, root, key):
# Initialize floor and ceil values to -1, indicating not found
floor = -1
ceil = -1
# Find the floor value
# Start from the root of the BST
current = root
while current:
# If the key matches the current node's value
if current.data == key:
# Set floor to this value
floor = current.data
break
# If the key is greater than the current node's value
# Update floor to the current node's value
# If the key is smaller than the current node's value
# Move to the left subtree to find a smaller value
elif current.data < key:
floor = current.data
current = current.right
else:
current = current.left
# Find the ceil value
# Reset current to start from the root again
current = root
while current:
# If the key matches the current node's value
if current.data == key:
# Set ceil to this value
ceil = current.data
break
# If the key is smaller than the current node's value
# Update ceil to the current node's value
# If the key is greater than the current node's value
# Move to the right subtree to find a larger value
elif current.data > key:
ceil = current.data
current = current.left
else:
current = current.right
# Return floor and ceil values as a list
return [floor, ceil]
if __name__ == "__main__":
# Creating a sample BST
root = TreeNode(8)
root.left = TreeNode(4)
root.right = TreeNode(12)
root.left.left = TreeNode(2)
root.left.right = TreeNode(6)
root.right.left = TreeNode(10)
root.right.right = TreeNode(14)
sol = Solution()
key = 11 # Key to find floor and ceil for
# Find and print floor and ceil values
result = sol.floorCeilOfBST(root, key)
print(f"Floor: {result[0]}, Ceil: {result[1]}")
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
// Definition for a binary tree node.
class TreeNode {
constructor(val = 0, left = null, right = null){
this.data = val;
this.left = null;
this.right = null;
}
}
class Solution {
floorCeilOfBST(root, key) {
// Initialize floor and ceil values to -1, indicating not found
let floor = -1;
let ceil = -1;
// Find the floor value
// Start from the root of the BST
let current = root;
while (current !== null) {
// If the key matches the current node's value
if (current.data === key) {
// Set floor to this value
floor = current.data;
break;
/* If the key is greater than the current node's value
Update floor to the current node's value
If the key is smaller than the current node's value
Move to the left subtree to find a smaller value */
} else if (current.data < key) {
floor = current.data;
current = current.right;
} else {
current = current.left;
}
}
// Find the ceil value
// Reset current to start from the root again
current = root;
while (current !== null) {
// If the key matches the current node's value
if (current.data === key) {
// Set ceil to this value
ceil = current.data;
break;
/* If the key is smaller than the current node's value
Update ceil to the current node's value
If the key is greater than the current node's value
Move to the right subtree to find a larger value */
} else if (current.data > key) {
ceil = current.data;
current = current.left;
} else {
current = current.right;
}
}
// Return floor and ceil values as an array
return [floor, ceil];
}
}
// Helper function to create a sample BST and find floor and ceil values
function main() {
// Creating a sample BST
let root = new TreeNode(8);
root.left = new TreeNode(4);
root.right = new TreeNode(12);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(6);
root.right.left = new TreeNode(10);
root.right.right = new TreeNode(14);
let sol = new Solution();
let key = 11; // Key to find floor and ceil for
// Find and print floor and ceil values
let result = sol.floorCeilOfBST(root, key);
console.log("Floor: " + result[0] + ", Ceil: " + result[1]);
}
// Execute the main function
main();
