Floor and Ceil in BST in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floor Value in BST

What is the floor value of 15 in the given BST after running the code?

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function floorInBST(root, key) {
  let floor = -1;
  while (root) {
    if (root.val === key) return root.val;
    if (root.val > key) root = root.left;
    else {
      floor = root.val;
      root = root.right;
    }
  }
  return floor;
}

// BST structure
//       10
//      /  \
//     5   20
//    / \    \
//   3   7   30

const root = new Node(10);
root.left = new Node(5);
root.right = new Node(20);
root.left.left = new Node(3);
root.left.right = new Node(7);
root.right.right = new Node(30);

console.log(floorInBST(root, 15));

A 10

B 7

C -1

D 20

💡 Hint

Floor is the greatest value less than or equal to the key.

The floor of 15 is the greatest value in the BST less than or equal to 15. Values less than 15 are 10, 5, 3, 7. The greatest among these is 10.

❓ Predict Output

intermediate

Output of Ceil Value in BST

What is the ceil value of 6 in the given BST after running the code?

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function ceilInBST(root, key) {
  let ceil = -1;
  while (root) {
    if (root.val === key) return root.val;
    if (root.val < key) root = root.right;
    else {
      ceil = root.val;
      root = root.left;
    }
  }
  return ceil;
}

// BST structure
//       10
//      /  \
//     5   20
//    / \    \
//   3   7   30

const root = new Node(10);
root.left = new Node(5);
root.right = new Node(20);
root.left.left = new Node(3);
root.left.right = new Node(7);
root.right.right = new Node(30);

console.log(ceilInBST(root, 6));

A -1

B 5

C 10

D 7

💡 Hint

Ceil is the smallest value greater than or equal to the key.

The ceil of 6 is the smallest value in the BST greater than or equal to 6. Values greater than 6 are 7, 10, 20, 30. The smallest among these is 7.

🧠 Conceptual

advanced

Understanding Floor and Ceil in BST

Which statement correctly describes the difference between floor and ceil in a BST for a given key?

A Floor is the smallest value greater than or equal to the key; Ceil is the greatest value less than or equal to the key.

B Floor and Ceil both return the exact key value if it exists; otherwise, they return -1.

C Floor is the greatest value less than or equal to the key; Ceil is the smallest value greater than or equal to the key.

D Floor returns the closest value to the key on the right subtree; Ceil returns the closest value on the left subtree.

💡 Hint

Think about which values are less than or greater than the key.

Floor is the greatest value in the BST that is less than or equal to the key. Ceil is the smallest value in the BST that is greater than or equal to the key.

🔧 Debug

advanced

Identify the Bug in Floor Function

What error will occur when running the following floor function code on a BST?

DSA Javascript

function floorInBST(root, key) {
  let floor = null;
  while (root) {
    if (root.val === key) return root.val;
    if (root.val < key) {
      floor = root.val;
      root = root.right;
    } else {
      root = root.left;
    }
  }
  return floor;
}

A Throws TypeError because floor is initialized as null.

B Returns incorrect floor value because traversal direction is wrong.

C Returns -1 always because root is never updated.

D Runs correctly and returns the correct floor value.

💡 Hint

Check which subtree to traverse when node value is less or greater than key.

The traversal directions are swapped. When root.val < key, we should go right to find a larger floor candidate, not left. Similarly, when root.val > key, we should go left.

🚀 Application

expert

Find Floor and Ceil for Multiple Keys in BST

Given the BST and keys array [4, 14, 25], what is the combined output of floor and ceil for each key?

DSA Javascript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function floorInBST(root, key) {
  let floor = -1;
  while (root) {
    if (root.val === key) return root.val;
    if (root.val > key) root = root.left;
    else {
      floor = root.val;
      root = root.right;
    }
  }
  return floor;
}

function ceilInBST(root, key) {
  let ceil = -1;
  while (root) {
    if (root.val === key) return root.val;
    if (root.val < key) root = root.right;
    else {
      ceil = root.val;
      root = root.left;
    }
  }
  return ceil;
}

// BST structure
//       15
//      /  \
//     10   20
//    / \    \
//   5  12   30

const root = new Node(15);
root.left = new Node(10);
root.right = new Node(20);
root.left.left = new Node(5);
root.left.right = new Node(12);
root.right.right = new Node(30);

const keys = [4, 14, 25];
const result = keys.map(k => ({ key: k, floor: floorInBST(root, k), ceil: ceilInBST(root, k) }));
console.log(result);

A [{"key":4,"floor":-1,"ceil":5},{"key":14,"floor":12,"ceil":15},{"key":25,"floor":20,"ceil":30}]

B [{"key":4,"floor":5,"ceil":10},{"key":14,"floor":10,"ceil":20},{"key":25,"floor":15,"ceil":30}]

C [{"key":4,"floor":-1,"ceil":10},{"key":14,"floor":12,"ceil":20},{"key":25,"floor":20,"ceil":-1}]

D [{"key":4,"floor":-1,"ceil":5},{"key":14,"floor":10,"ceil":15},{"key":25,"floor":20,"ceil":30}]

💡 Hint

Check floor and ceil for each key individually using BST traversal rules.

For key=4, floor doesn't exist (-1), ceil is 5. For 14, floor is 12 (largest ≤14), ceil is 15 (smallest ≥14). For 25, floor is 20, ceil is 30.