Floor and Ceil in BST in DSA C - Execution Trace

Concept Flow - Floor and Ceil in BST

Start at root node

↓

Compare key with current node value

↓

Go left

↓

Update ceil

↓

Repeat until leaf or exact match

↓

Return floor and ceil values

Start from the root, compare the key with current node value, move left or right updating floor or ceil accordingly, until you find exact match or reach leaf.

Execution Sample

DSA C

int floorBST(Node* root, int key) {
  int 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;
}

Find floor value in BST for given key by traversing and updating floor when moving right.

Execution Table

Step	Operation	Current Node	Key	Floor	Ceil	Pointer Move	Visual State
1	Start at root	20	18	-1	-1	Compare 18 < 20	20 / \ 10 30
2	Go left	10	18	-1	20	18 > 10, floor=10, move right	20 / \ 10 30
3	Go right	15	18	10	20	18 > 15, floor=15, move right	20 / \ 10 30 \ 15
4	Go right	17	18	15	20	18 > 17, floor=17, move right	20 / \ 10 30 \ 15 \ 17
5	Go right	NULL	18	17	20	Reached leaf, stop	20 / \ 10 30 \ 15 \ 17
6	Return	-	18	17	20	Floor=17, Ceil=20	Final floor=17, ceil=20

💡 Traversal ends when pointer reaches NULL (leaf), floor and ceil are last updated values.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
root->val	20	20	10	15	17	NULL	NULL
floor	-1	-1	10	15	17	17	17
ceil	-1	20	20	20	20	20	20
pointer move	N/A	left	right	right	right	stop	stop

Key Moments - 3 Insights

Why do we update floor only when moving right?

Because when key is greater than current node, current node could be floor. See execution_table rows 2-4 where floor updates when moving right.

Why do we update ceil only when moving left?

Because when key is less than current node, current node could be ceil. In the example, ceil updates at step 2 when moving left from 20.

What happens if key matches a node value exactly?

We return that node's value immediately as both floor and ceil. This is shown in code line: if (root->val == key) return root->val;

Visual Quiz - 3 Questions

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

A 10

B 17

C 15

D -1

💡 Hint

Check the 'Floor' column in execution_table row for step 3.

At which step does the pointer reach NULL, ending traversal?

A Step 4

B Step 5

C Step 6

D Step 3

💡 Hint

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

If the key was 25 instead of 18, how would the floor value change after step 2?

A Floor would be 20

B Floor would be -1

C Floor would be 10

D Floor would be 15

💡 Hint

Consider how floor updates when key > current node, see variable_tracker and execution_table.

Concept Snapshot

Floor and Ceil in BST:
- Floor: greatest value <= key
- Ceil: smallest value >= key
- Traverse from root:
  * If node val == key, return it
  * If node val > key, move left, update ceil
  * If node val < key, move right, update floor
- Stop at leaf, return last floor and ceil

Full Transcript

To find floor and ceil in a BST for a given key, start at the root node. Compare the key with the current node's value. If they are equal, return that value immediately as both floor and ceil. If the key is less than the current node's value, move to the left child and update the ceil to current node's value because it might be the smallest value greater than or equal to the key. If the key is greater than the current node's value, move to the right child and update the floor to current node's value because it might be the greatest value less than or equal to the key. Continue this process until you reach a leaf node (NULL). Then return the last updated floor and ceil values. This method efficiently finds floor and ceil by leveraging BST properties.

Practice

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

easy

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

B. The root value of the BST

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

D. The smallest value in the BST less than the given value

Solution

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

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

2. Step 2: Compare with options

   The greatest value in the BST less than or equal to the given value matches this definition exactly, while others describe different concepts.

3. Final Answer:

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

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 is the correct C function signature to find the ceil of a value in a BST node structure named Node?

easy

A. int ceilBST(Node* root, int key);

B. void ceilBST(Node root, int key);

C. Node* ceilBST(int key, Node* root);

D. int ceilBST(int key);

Solution

1. Step 1: Analyze function parameters and return type

   The function should take a pointer to the root node and the key to find ceil for, returning an integer value.

2. Step 2: Match with options

   int ceilBST(Node* root, int key); matches this: it takes Node* root and int key, returns int. Others have wrong parameter order, types, or return type.

3. Final Answer:

   int ceilBST(Node* root, int key); -> Option A

4. Quick Check:

   Correct signature: pointer root, key, returns int [OK]

Hint: Function takes root pointer and key, returns int [OK]

Common Mistakes:

• Passing root by value instead of pointer
• Wrong parameter order
• Returning Node* instead of int

3. Given the BST below and the key = 14, what is the output of the ceil function?

        10
       /  \
      5    15
          /  \
         12   20

medium

A. -1

B. 15

C. 12

D. 20

Solution

1. Step 1: Understand ceil definition and traverse BST

   Ceil is smallest value ≥ key. Starting at root 10, since 14 > 10, move right to 15. 15 ≥ 14, so candidate ceil is 15. Check left subtree of 15 (12) which is < 14, so ignore.

2. Step 2: Confirm smallest candidate

   15 is the smallest node ≥ 14. 20 is larger but not smaller than 15, so 15 is ceil.

3. Final Answer:

   15 -> Option B

4. Quick Check:

   Ceil(14) = 15 [OK]

Hint: Ceil is smallest node ≥ key, check right subtree carefully [OK]

Common Mistakes:

• Choosing 20 instead of 15
• Choosing 12 which is < 14
• Returning -1 when ceil exists

4. Consider the following buggy C code snippet to find floor in BST. What is the main error?

int floorBST(Node* root, int key) {
    if (!root) return -1;
    if (root->data == key) return root->data;
    if (root->data > key) return floorBST(root->left, key);
    int floorValue = floorBST(root->right, key);
    if (floorValue <= key && floorValue != -1) return floorValue;
    else return root->data;
}

medium

A. It returns root->data even if floorValue is -1

B. It does not check for NULL root

C. It returns -1 when key is found

D. It incorrectly searches left subtree when root->data < key

Solution

1. Step 1: Analyze return conditions

   If floorValue is -1 (meaning no floor found in right subtree), the code returns root->data without checking if root->data ≤ key, which can be incorrect.

2. Step 2: Identify the error

   The code should check if root->data ≤ key before returning it; otherwise, it may return a value greater than key, violating floor definition.

3. Final Answer:

   It returns root->data even if floorValue is -1 -> Option A

4. Quick Check:

   Missing check before returning root->data causes wrong floor [OK]

Hint: Check root->data ≤ key before returning it [OK]

Common Mistakes:

• Ignoring floorValue == -1 case
• Returning wrong subtree
• Not handling NULL root

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

hard

A. Floor = 5, Ceil = 5

B. Floor = 6, Ceil = 4

C. Floor = 2, Ceil = 8

D. Floor = 4, Ceil = 6

Solution

1. Step 1: Identify floor of 5 in BST

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

2. Step 2: Identify ceil of 5 in BST

   Ceil is smallest value ≥ 5. Nodes ≥ 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 wrong closest values