Floor and Ceil in BST in DSA Typescript - Execution Trace

Concept Flow - Floor and Ceil in BST

Start at root

↓

Compare target with current node

↓

Go right

↓

Update floor

↓

Repeat until leaf

↓

Return floor and ceil

Start at the root, compare target with current node value, move left or right updating floor or ceil until reaching a leaf, then return the found floor and ceil.

Execution Sample

DSA Typescript

function floorCeilBST(root, target) {
  let floor = null, ceil = null;
  let current = root;
  while (current) {
    if (current.val === target) return { floor: current.val, ceil: current.val };
    else if (current.val < target) {
      floor = current.val;
      current = current.right;
    } else {
      ceil = current.val;
      current = current.left;
    }
  }
  return { floor, ceil };
}

Find floor and ceil of target in BST by traversing from root, updating floor or ceil based on comparison.

Execution Table

Step	Operation	Current Node	Comparison	Floor	Ceil	Pointer Move	Visual State
1	Start at root	10	10 vs 14	null	null	Move right	10
2	Compare	15	15 vs 14	10	null	Move left	10 -> 15
3	Compare	12	12 vs 14	12	null	Move right	10 -> 15 -> 12
4	Compare	13	13 vs 14	13	null	Move right	10 -> 15 -> 12 -> 13
5	Compare	null	Reached leaf	13	null	Stop	10 -> 15 -> 12 -> 13
6	Return	N/A	N/A	13	null	N/A	Floor=13, Ceil=null

💡 Reached leaf node with no further children to explore.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
floor	null	null	10	12	13	13	13
ceil	null	null	null	null	null	null	null
current	root(10)	15	12	13	null	null	null

Key Moments - 3 Insights

Why do we update floor only when current node value is less than target?

Because floor is the greatest value less than or equal to target. When current node is less than target, it can be a candidate floor. See execution_table steps 2-4 where floor updates.

Why do we move left when current node value is greater than target?

Because all values in left subtree are smaller, so potential ceil (smallest value >= target) might be there. See execution_table step 2 where we move left after finding 15 > 14.

What if target equals a node value?

We return that node value as both floor and ceil immediately, since exact match means floor and ceil are the same. This is shown in the code but not in this trace.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the floor value?

A 10

B 12

C null

D 13

💡 Hint

Check the 'Floor' column at step 3 in execution_table.

At which step does the pointer move to a null node, stopping the traversal?

A Step 4

B Step 5

C Step 3

D Step 2

💡 Hint

Look at the 'Current Node' and 'Pointer Move' columns in execution_table.

If the target was 15 instead of 14, what would be the returned floor and ceil?

A Floor=15, Ceil=15

B Floor=13, Ceil=15

C Floor=14, Ceil=15

D Floor=10, Ceil=12

💡 Hint

Recall the code returns exact match as floor and ceil immediately.

Concept Snapshot

Floor and Ceil in BST:
- Floor: greatest value <= target
- Ceil: smallest value >= target
- Start at root, compare target with node
- Move right if node < target (update floor)
- Move left if node > target (update ceil)
- Stop at leaf, return floor and ceil

Full Transcript

To find floor and ceil in a Binary Search Tree (BST), start at the root node. Compare the target value with the current node's value. If the current node's value equals the target, return it as both floor and ceil. If the current node's value is less than the target, update floor to current node's value and move to the right child. If greater, update ceil to current node's value and move to the left child. Repeat until reaching a leaf node (null). Then return the last updated floor and ceil values. This process efficiently finds the closest values less than or equal to (floor) and greater than or equal to (ceil) the target in the BST.

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