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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floor and Ceil for a given key in BST

What is the output of the floor and ceil values for key 15 in the given BST after running the code?

DSA Typescript

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

function insert(root: Node | null, val: number): Node {
  if (!root) return new Node(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

function floor(root: Node | null, key: number): number | null {
  let res: number | null = null;
  while (root) {
    if (root.val === key) return root.val;
    if (root.val > key) root = root.left;
    else {
      res = root.val;
      root = root.right;
    }
  }
  return res;
}

function ceil(root: Node | null, key: number): number | null {
  let res: number | null = null;
  while (root) {
    if (root.val === key) return root.val;
    if (root.val < key) root = root.right;
    else {
      res = root.val;
      root = root.left;
    }
  }
  return res;
}

const values = [10, 5, 18, 3, 7, 12, 20];
let root: Node | null = null;
for (const v of values) {
  root = insert(root, v);
}

const key = 15;
const floorVal = floor(root, key);
const ceilVal = ceil(root, key);
console.log(`Floor: ${floorVal}, Ceil: ${ceilVal}`);

A Floor: 12, Ceil: 18

B Floor: 10, Ceil: 12

C Floor: 15, Ceil: 15

D Floor: 7, Ceil: 20

💡 Hint

Trace the BST traversal for floor and ceil separately, comparing node values with the key.

The floor is the greatest value less than or equal to the key. For 15, the floor is 12.

The ceil is the smallest value greater than or equal to the key. For 15, the ceil is 18.

🧠 Conceptual

intermediate

Number of nodes visited in floor search

In the worst case, how many nodes does the floor function visit in a BST with n nodes?

A O(1) node

B O(log n) nodes

C O(n) nodes

D O(n log n) nodes

💡 Hint

Consider the shape of the BST in the worst case (like a linked list).

In the worst case, the BST is skewed, so floor function visits all nodes along the path, which can be O(n).

🔧 Debug

advanced

Identify the error in ceil function implementation

What error will occur when running this ceil function on a BST if the key is larger than all nodes?

DSA Typescript

function ceil(root: Node | null, key: number): number {
  let res: number | null = null;
  while (root) {
    if (root.val === key) return root.val;
    if (root.val < key) root = root.right;
    else {
      res = root.val;
      root = root.left;
    }
  }
  return res!;
}

A Returns null without error

B Throws a runtime error due to null assertion

C Returns incorrect ceil value

D Infinite loop

💡 Hint

What happens if res remains null and you use the non-null assertion operator?

If the key is larger than all nodes, res stays null. Using res! forces a non-null return, causing a runtime error.

❓ Predict Output

advanced

Output after inserting nodes and finding floor and ceil

What is the output after inserting nodes [8, 4, 12, 2, 6, 10, 14] and finding floor and ceil for key 5?

DSA Typescript

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

function insert(root: Node | null, val: number): Node {
  if (!root) return new Node(val);
  if (val < root.val) root.left = insert(root.left, val);
  else root.right = insert(root.right, val);
  return root;
}

function floor(root: Node | null, key: number): number | null {
  let res: number | null = null;
  while (root) {
    if (root.val === key) return root.val;
    if (root.val > key) root = root.left;
    else {
      res = root.val;
      root = root.right;
    }
  }
  return res;
}

function ceil(root: Node | null, key: number): number | null {
  let res: number | null = null;
  while (root) {
    if (root.val === key) return root.val;
    if (root.val < key) root = root.right;
    else {
      res = root.val;
      root = root.left;
    }
  }
  return res;
}

const values = [8, 4, 12, 2, 6, 10, 14];
let root: Node | null = null;
for (const v of values) {
  root = insert(root, v);
}

const key = 5;
const floorVal = floor(root, key);
const ceilVal = ceil(root, key);
console.log(`Floor: ${floorVal}, Ceil: ${ceilVal}`);

A Floor: 2, Ceil: 4

B Floor: 6, Ceil: 8

C Floor: 5, Ceil: 5

D Floor: 4, Ceil: 6

💡 Hint

Check nodes less than and greater than 5 in the BST.

Floor is the greatest value less than or equal to 5, which is 4.

Ceil is the smallest value greater than or equal to 5, which is 6.

🧠 Conceptual

expert

Effect of BST shape on floor and ceil efficiency

How does the shape of a BST affect the efficiency of floor and ceil operations?

A Balanced BST gives O(log n) time; skewed BST gives O(n) time

B Shape does not affect efficiency; always O(log n)

C Skewed BST gives O(1) time; balanced BST gives O(n) time

D Efficiency depends only on the key value, not BST shape

💡 Hint

Consider the height of the tree and path length for search.

Balanced BST has height about log n, so floor and ceil run in O(log n).

Skewed BST is like a linked list, so operations degrade to O(n).