Given a binary search tree and an integer.Find the floor value of a key in a binary search tree .
(If k lies in BST then is floor equal to k,else floor is equal to previous greater value) Note: k would never be less than the minimum element of tree.
Line 1: Integer k (separated by space)
Line 2 : Elements in level order form
(If any node does not have left or right child, take -1 in its place)
Floor of integer k from given BST
for the above tree
k=2
floor=1
k=7
floor=7
k=12
floor=10
4
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
2
7
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
7
All tags
Sort by
Interview problems
Recursive solution c++ | easy begginers
int ans;
void dfs (BinaryTreeNode<int> *node, int x){
if(!node)return;
if(node->data == x){
ans=node->data;
return;
}
if (node->data >= x) {
dfs(node->left, x);
}
else{
ans=node->data;
dfs(node->right, x);
}
}
int Floor(BinaryTreeNode<int> *node, int input)
{
/*Write your code here.
*Don't write main().
*Don't take input, it is passed as function argument.
*Don't print output.
*Taking input and printing output is handled automatically.
*/
ans=-1;
dfs(node,input);
return ans;
}
Interview problems
Sample Test Case-3 has 'INVALID BST'
test case 3 has invalid BST if your code is giving correct output for first 2 sample test cases , simply submit it :)
Interview problems
C++ soln_ with TC->O(log2N)!!
int Floor(BinaryTreeNode<int> *node, int input)
{
int floor = -1;
while(node){
if(node->data == input){
floor = node->data;
return floor;
}
if(input < node->data){
node = node->left;
}
else{
floor = node->data;
node = node->right;
}
}
return floor;
}
Interview problems
TESTCASE-3 has INVALID BST
Click here for better understanding.
int Floor(BinaryTreeNode<int> *node, int x){
int ans=-1;
while(node){
if(node->data==x)
return node->data;
if(node->data<=x){
ans=node->data;
node=node->right;
}else
node=node->left;
}
return ans;
}
// BELOW CODE SHOULD WORK, BUT NOT RUNNING DUE TO INVALID TESTCASE.
// int ans=-1;
// while(node){
// if(node->data<=x){
// ans=node->data;
// node=node->right;
// }else
// node=node->left;
// }
// return ans;
// }Interview problems
What is the error in this code???
int Floor(BinaryTreeNode<int> *node, int input)
{
int res = -1;
if(node==NULL){
return -1;
}
while(node!=NULL){
if(node->data > input){
node = node->left;
}
else{
res = node->data;
node = node->right;
}
}
return res;
}
Interview problems
C++ | Iterative | Easy to understand
int Floor(BinaryTreeNode<int> *root, int x)
{
/*Write your code here.
*Don't write main().
*Don't take input, it is passed as function argument.
*Don't print output.
*Taking input and printing output is handled automatically.
*/
// Write your code here.
int lower=-1;
while(root!=NULL){
if(root->data==x){
lower=root->data;
return lower;
}
if(root->data<x){
lower=root->data;
root=root->right;
}
else{
root=root->left;
}
}
return lower;
}
Interview problems
cpp recursion
int Floor(BinaryTreeNode<int> *node, int input)
{
/*Write your code here.
*Don't write main().
*Don't take input, it is passed as function argument.
*Don't print output.
*Taking input and printing output is handled automatically.
*/
if(!node){
return -1;
}
if(node->data==input){
return node->data;
}
if(node->data>input){
return Floor(node->left,input);
}else{
int floorValue=Floor(node->right,input);
return (floorValue!=-1)?floorValue:node->data;
}
}
Interview problems
Floor in a BST (Java Solution)
public static int Floor(BinaryTreeNode<Integer> node, int input) {
return helper(node,input,-1);
}
private static int helper(BinaryTreeNode<Integer> root,int x,int floor){
if(root==null)
return floor;
if(x>=root.data){
if(floor<root.data)
floor=root.data;
return helper(root.right,x,floor);
}
else {
return helper(root.left,x,floor);
}
}
Interview problems
FLOOR IN A BST
int Floor(BinaryTreeNode<int> *node, int input)
{
int floor=-1;
while(node){
if(node->data == input)
return input;
else if(node->data<input){
floor=node->data;
node=node->right;
}
else node=node->left;
}
return floor;
}
Interview problems
Cpp
int Floor(BinaryTreeNode<int> *node, int input){
if(node == NULL){
return -1;
}
if(node-> data <= input){
int floor = Floor(node->right , input);
return floor != -1 && floor > node->data ? floor :node->data ;
} else return Floor(node->left , input);
}
