Floor of a value in BST

Question

Given a value and a BST , we need to find the largest number which is just smaller or equal to the given value , i.e. , the floor of the value. For example, 1 4 7 9 12 13 43 45 is the given inOrder traversal of the BST and we are given a value 15 .

So floor(15) = 13 , floor(10) = 9 , etc.

I was doing inOrder traversal and maintaining a previous node and if the value is between data of previous and root node then returnt that value as floor. However, it doesn't work for all cases.

Also since it is a BST we dont need to do complete traversal , we can make use of BST property. But I am not able to convert my logic into code. So can anyone please help with it?

Preferably in Java. We need to use it in our project in which we are sort of creating a new language based on Java.

Answer 1

The following working Java code solves this problem in O(log N) time.

The logic is very simple. If the value in the current node is smaller than val, then look for a greater value in the right sub-tree of the current node, or look for an answer in the left subtree.

void run(){
      Obj root = new Obj(1);
      root = insertVal(root, 4);
      root = insertVal(root, 7);
      root = insertVal(root, 9);
      root = insertVal(root, 12);
      root = insertVal(root, 13);
      root = insertVal(root, 43);
      root = insertVal(root, 45);
      System.out.println(floor(root, 15));
 }

 // throws a RuntimeException if there is no smaller value in the BST.
 int floor(Obj root, int val){
     int ans = Integer.MIN_VALUE;
     boolean found = false;
     while(root != null){
         if(root.val==val){
             return val;
         }
         if(val < root.val){
             root = root.left;
         }else{
            found = true;
             ans = root.val;
             root = root.right;
         }
     }
     if(!found){
        throw new RuntimeException("There is no smaller value than " + val + " in the BST");
     }
     return ans;
 }

 Obj insertVal(Obj root, int val){
     if(root==null){
         return new Obj(val);
     }
     if(val < root.val){
         root.left = insertVal(root.left, val);
     }else{
         root.right = insertVal(root.right, val);
     }
     return root;
 }
}
class Obj{
 int val;
 Obj right;
 Obj left;

 public Obj(int val){
      this.val = val;
      right = left = null;
 }

 public String toString(){
      return val + " ";
 }
}