Find floor and ceil of binary search tree

Given a binary search tree and key, if there exists a node in the tree with same value as the key then its floor and ceil value are same as the key, else the node which has lesser value than the key will be the floor and the node with greater value will be the ceil.

Example

Input:
      8
     /   \
    /     \
   4       10
  / \     /  \
 /   \   /    \
2     6 9     12

key = 11;

Output:
floor: 10;
ceil: 12;

We are going to see the both recursive as well as the iterative solution for it.

Recursive solution: Floor and Ceil of binary search tree.

Conceptually this is how it works

• Use an object with floor and ceil key to store the values from the tree.
• We create a recursive function and check if the given key exists as a node value in the tree then update the floor and ceil value.
• Else recursively search for the given key in the tree.
• If the current node’s value is less than key then update the ceil value to the node’s value and recur for the left subtree.
• If the current node’s value is greater than key then update the floor value to the node’s value and recur for the right subtree.
• At the end we will have the floor and ceil value if the key doesn’t exists.

const floorCeilRecursive = (root, key, store) => {
  //base case
  if(root === null){
    return;
  }
  
  //if node with key value is found then both floor and ceil are same value
  if(root.val === key){
    store.floor = root.val;
    store.ceil = root.val;
  }
  
  //if the key is less than the node value, then recur for left subtree
  else if(key < root.val){
    //update the ceil value before recur
    store.ceil = root.val;
    floorCeil(root.left, key, store);
  }
  
  //If key is greater than the node value, then recur for right subtree
  else{
    //update the floor value before recur
    store.floor = root.val;
    floorCeil(root.right, key, store);
  }
}

Input:
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

const tree = new Node(8);  
tree.left = new Node(4);  
tree.right = new Node(10);  
tree.left.left = new Node(2);  
tree.left.right = new Node(6);  
tree.right.left = new Node(9);  
tree.right.right = new Node(12);

Output:
const store = {
  floor: -1,
  ceil: -1
}

floorCeilRecursive(tree, 7, store);
console.log(store);
{
  floor: 6,
  ceil: 8
}

Time complexity: O(n).
Space complexity: O(n) if call stack is considered. O(1) otherwise.

---

Iterative solution

We can convert the same recursive solution to the iterative one by using while loop.

const floorCeilIterative = (root, key, store) => {
  //base case
  while(root !== null){
    //if node with key value is found then both floor and ceil are same value
    if(root.val === key){
      store.floor = root.val;
      store.ceil = root.val;
      break;
    }

    //if the key is less than the node value, then recur for left subtree
    else if(key < root.val){
      //update the ceil value before recur
      store.ceil = root.val;
      root = root.left;
    }

    //If key is greater than the node value, then recur for right subtree
    else{
      //update the floor value before recur
      store.floor = root.val;
      root = root.right;
    }
  }
}

Input:
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

const tree = new Node(8);  
tree.left = new Node(4);  
tree.right = new Node(10);  
tree.left.left = new Node(2);  
tree.left.right = new Node(6);  
tree.right.left = new Node(9);  
tree.right.right = new Node(12);

Output:
const store = {
  floor: -1,
  ceil: -1
}

floorCeilIterative(tree, 7, store);
console.log(store);
{
  floor: 6,
  ceil: 8
}

Time complexity: O(n).
Space complexity: O(1).