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).

Practice

1. What does the floor of a value in a Binary Search Tree (BST) represent?

easy

A. The greatest value in the BST less than or equal to the given value

B. The smallest value in the BST greater than or equal to the given value

C. The root value of the BST

D. The average of all values in the BST

Solution

1. Step 1: Understand the definition of floor in BST

   The floor of a value in BST is the greatest value that is less than or equal to the given value.

2. Step 2: Compare with other options

   The smallest value in the BST greater than or equal to the given value describes ceil, not floor. Options C and D are unrelated to floor concept.

3. Final Answer:

   The greatest value in the BST less than or equal to the given value -> Option A

4. Quick Check:

   Floor = greatest ≤ value [OK]

Hint: Floor is largest value ≤ target in BST [OK]

Common Mistakes:

• Confusing floor with ceil
• Thinking floor is the smallest value
• Assuming floor is always the root

2. Which of the following TypeScript function signatures correctly represents a function to find the ceil in a BST?

easy

A. function findCeil(key: number, root: TreeNode): number

B. function findCeil(root: TreeNode | null, key: number): number | null

C. function findCeil(root: TreeNode, key: string): number

D. function findCeil(root: TreeNode | null): number

Solution

1. Step 1: Check parameter order and types

   Function should accept root node (possibly null) and a key number to find ceil for.

2. Step 2: Validate return type

   Return type should be number or null if no ceil found. function findCeil(root: TreeNode | null, key: number): number | null matches this.

3. Final Answer:

   function findCeil(root: TreeNode | null, key: number): number | null -> Option B

4. Quick Check:

   Correct params and return type [OK]

Hint: Root first, key second, return number or null [OK]

Common Mistakes:

• Swapping parameter order
• Using wrong parameter types
• Missing null in root type

3. Given the BST below and key = 14, what is the ceil value?

       10
      /  \
     5    15
         /  \
        12   20

medium

A. 12

B. 20

C. 15

D. null

Solution

1. Step 1: Locate key 14 in BST or nearest nodes

   14 is not in BST. Check nodes greater than or equal to 14: 15 and 20.

2. Step 2: Find smallest node ≥ 14

   Between 15 and 20, 15 is smaller and ≥ 14, so ceil is 15.

3. Final Answer:

   15 -> Option C

4. Quick Check:

   Ceil = smallest ≥ 14 is 15 [OK]

Hint: Ceil is smallest value ≥ key in BST [OK]

Common Mistakes:

• Choosing 12 which is less than 14
• Choosing 20 which is larger but not smallest ≥ 14
• Returning null when ceil exists

4. Consider this TypeScript function to find floor in BST:

function findFloor(root: TreeNode | null, key: number): number | null {
  if (!root) return null;
  if (root.val === key) return root.val;
  const floorRight = findFloor(root.right, key);
  return floorRight !== null ? floorRight : root.val;
}

What is the bug in this code?

medium

A. It returns root.val even if floorRight is null and root.val > key

B. It does not check for null root

C. It returns key instead of floor value

D. It incorrectly calls findFloor on root.left when root.val < key

Solution

1. Step 1: Identify missing logic for root.val > key

   The code does not recurse into the left subtree when root.val > key. Instead, it always computes floorRight from the right subtree.

2. Step 2: Trace buggy return

   When root.val > key and right subtree yields null for floorRight (common case), it returns root.val which exceeds key, violating floor definition.

3. Final Answer:

   It returns root.val even if floorRight is null and root.val > key -> Option A

4. Quick Check:

   Missing left recursion on root.val > key [OK]

Hint: Check return when right subtree floor is null [OK]

Common Mistakes:

• Ignoring null checks
• Confusing left and right subtree calls
• Assuming root.val always valid floor

5. You have a BST with values [8, 4, 12, 2, 6, 10, 14]. You want to find the floor and ceil of 5. Which pair is correct?

medium

A. Floor = 2, Ceil = 8

B. Floor = 6, Ceil = 4

C. Floor = 5, Ceil = 5

D. Floor = 4, Ceil = 6

Solution

1. Step 1: Identify floor of 5 in BST

   Floor is greatest value ≤ 5. Values ≤ 5 are 2 and 4. Greatest is 4.

2. Step 2: Identify ceil of 5 in BST

   Ceil is smallest value ≥ 5. Values ≥ 5 are 6, 8, 10, 12, 14. Smallest is 6.

3. Final Answer:

   Floor = 4, Ceil = 6 -> Option D

4. Quick Check:

   Floor ≤ 5 = 4, Ceil ≥ 5 = 6 [OK]

Hint: Floor ≤ key, Ceil ≥ key; pick closest values [OK]

Common Mistakes:

• Swapping floor and ceil values
• Assuming floor or ceil equals key if not present
• Choosing values not in BST