Floor and Ceil in BST in DSA C++ - Execution Trace

Concept Flow - Floor and Ceil in BST

Start at root

↓

Compare key with current node

↓

Floor = Ceil = node value

→Done

↓

Go to left subtree

↓

Record node value as potential floor

↓

Go to right subtree

↓

Repeat until no more nodes

↓

Return recorded floor or ceil value

Start at the root and compare the key with current node value. Move left if key is smaller, move right if key is larger, updating floor or ceil candidates until traversal ends.

Execution Sample

DSA C++

struct Node {
  int val;
  Node* left;
  Node* right;
};

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;
}

Finds the floor value (largest value <= key) in a BST by traversing from root and updating floor candidate.

Execution Table

Step	Operation	Current Node Value	Key	Floor Candidate	Ceil Candidate	Pointer Move	Visual State
1	Start at root	20	18	-1	null	Compare 18 with 20	20 / \ 10 30
2	Key < node value	20	18	-1	20	Move to left child	20 / \ 10 30
3	At node 10	10	18	-1	20	Compare 18 with 10	20 / \ 10 30
4	Key > node value	10	18	10	20	Move to right child	20 / \ 10 30
5	At node 15	15	18	10	20	Compare 18 with 15	20 / \ 10 30 \ 15
6	Key > node value	15	18	15	20	Move to right child	20 / \ 10 30 \ 15
7	At node null	null	18	15	20	No node, stop	20 / \ 10 30 \ 15
8	Return floor	null	18	15	20	Floor found: 15	Final floor = 15
9	Return ceil	null	18	15	20	Ceil found: 20	Final ceil = 20

💡 Traversal ends when pointer reaches null; floor and ceil candidates recorded during traversal.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	Final
Current Node	20	10	15	null	null
Floor Candidate	-1	-1	10	15	15
Ceil Candidate	null	20	20	20	20

Key Moments - 3 Insights

Why do we update the floor candidate only when current node value is less than the key?

Because floor is the largest value less than or equal to the key. When current node value is less than key, it can be a floor candidate. This is shown in execution_table rows 4 and 6 where floor updates to 10 and then 15.

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

Because all values in the right subtree will be even larger, so to find a floor or ceil closer to key, we move left. This is shown in execution_table row 2 where pointer moves left from 20 to 10.

How do we find the ceil value during traversal?

We update the ceil candidate when current node value is greater than or equal to the key. In this example, ceil is updated to 20 at step 2 and remains until traversal ends, as shown in variable_tracker.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the floor candidate value?

A 10

B -1

C 15

D 20

💡 Hint

Check the 'Floor Candidate' column at step 4 in the execution_table.

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

A Step 5

B Step 6

C Step 7

D Step 8

💡 Hint

Look for 'At node null' in the 'Current Node Value' column in execution_table.

If the key was 25 instead of 18, how would the floor candidate change at step 6?

A It would remain 15

B It would update to 20

C It would update to 30

D It would be -1

💡 Hint

Consider how floor updates when current node value is less than key, check variable_tracker for floor candidate updates.

Concept Snapshot

Floor and Ceil in BST:
- Floor: largest value <= key
- Ceil: smallest value >= key
- Start at root, compare key with node
- Move left if key < node, update ceil
- Move right if key > node, update floor
- Stop when no more nodes
- Return recorded floor and ceil

Full Transcript

To find floor and ceil in a BST, start at the root node. Compare the key with the current node's value. If equal, floor and ceil are the node's value. If key is less, move to the left child and update ceil candidate. If key is greater, move to the right child and update floor candidate. Continue until no nodes remain. The last recorded floor and ceil candidates are the results. This process efficiently finds the closest values less than or equal to (floor) and greater than or equal to (ceil) the key.

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

easy

A. int ceilBST(int val);

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

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

D. int ceilBST(Node* root, int val);

Solution

1. Step 1: Analyze function parameters and return type

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

2. Step 2: Check each option

   int ceilBST(Node* root, int val); matches correct signature: returns int, takes Node* and int. Others have wrong parameter order, missing pointers, or wrong return type.

3. Final Answer:

   int ceilBST(Node* root, int val); -> Option D

4. Quick Check:

   Correct signature returns int and takes Node* root [OK]

Hint: Function needs root pointer and value, returns int [OK]

Common Mistakes:

• Passing Node by value instead of pointer
• Wrong parameter order
• Incorrect return type

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

        10
       /  \
      5    15
          /  \
         12   20

medium

A. 12

B. 15

C. 20

D. 10

Solution

1. Step 1: Locate value 14 in BST context

   14 is not in BST. We look for smallest value ≥ 14.

2. Step 2: Check nodes greater than or equal to 14

   Nodes ≥14 are 15 and 20. The smallest among these is 15.

3. Final Answer:

   15 -> Option B

4. Quick Check:

   Ceil(14) = 15 [OK]

Hint: Ceil is smallest node ≥ target [OK]

Common Mistakes:

• Choosing 12 which is less than 14
• Choosing 20 which is larger but not smallest ≥14
• Confusing floor and ceil

4. Consider this buggy C++ code snippet to find floor in BST:

int floorBST(Node* root, int val) {
  if (!root) return -1;
  if (root->data == val) return root->data;
  if (root->data > val) return floorBST(root->left, val);
  int floorRight = floorBST(root->right, val);
  return (floorRight != -1 && floorRight <= val) ? floorRight : root->data;
}

What is the bug?

medium

A. It always returns root->data without recursion

B. It does not check for null root

C. It returns root->data when floorRight is greater than val, which is incorrect

D. It returns -1 for all values

Solution

1. Step 1: Understand the floor logic in code

   If root->data > val, search left subtree. Else search right subtree and compare.

2. Step 2: Identify incorrect return condition

   The code returns root->data if floorRight > val. However, since floorRight is never > val (returns -1 or ≤ val), this never triggers, causing it to return -1 (when right subtree has no floor ≤ val) instead of root->data.

3. Final Answer:

   It returns root->data when floorRight is greater than val, which is incorrect -> Option C

4. Quick Check:

   Floor must be ≤ val, code returns invalid value [OK]

Hint: Floor must never exceed val; check return conditions [OK]

Common Mistakes:

• Returning values greater than val as floor
• Missing null checks
• Ignoring recursion on left subtree

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

hard

A. Floor = 6, Ceil = 8

B. Floor = 8, Ceil = 6

C. Floor = 4, Ceil = 10

D. Floor = 7, Ceil = 7

Solution

1. Step 1: Identify floor of 7 in BST

   Floor is greatest value ≤7. Values ≤7 are 2,4,6. Greatest is 6.

2. Step 2: Identify ceil of 7 in BST

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

3. Final Answer:

   Floor = 6, Ceil = 8 -> Option A

4. Quick Check:

   Floor ≤7 = 6, Ceil ≥7 = 8 [OK]

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

Common Mistakes:

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