Floor and Ceil in BST in DSA Java - 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 node values, move left or right updating floor or ceil until you find exact match or reach leaf.

Execution Sample

DSA Java

class Node {
  int val;
  Node left, right;
}

int floor(Node root, int key) {
  // returns floor value
}

Find floor value of key in BST by traversing nodes comparing key and updating floor candidate.

Execution Table

Step	Operation	Current Node	Compare key with node	Floor Candidate	Ceil Candidate	Visual State
1	Start at root	20	key=18 < 20	null	20	20 / null null
2	Go left	10	key=18 > 10	10	20	20 / 10 null
3	Go right	15	key=18 > 15	15	20	20 / 10 null \ 15
4	Go right	17	key=18 > 17	17	20	20 / 10 null \ 15 \ 17
5	Go right	null	Reached leaf	17	20	20 / 10 null \ 15 \ 17
6	Return floor and ceil	null	No more nodes	17	20	Final floor=17, ceil=20

💡 Reached leaf node, no more nodes to traverse

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
Current Node	20	10	15	17	null	null	null
Floor Candidate	null	null	10	15	17	17	17
Ceil Candidate	null	20	20	20	20	20	20

Key Moments - 3 Insights

Why do we update the ceil candidate when key < node value?

Because the current node value is a potential ceil (smallest number >= key). See execution_table step 1 where ceil is updated to 20.

Why do we update the floor candidate when key > node value?

Because the current node value is a potential floor (largest number <= key). See execution_table steps 2 to 4 where floor updates from null to 10, then 15, then 17.

What happens when we reach a null node?

Traversal stops as there are no more nodes. The last updated floor and ceil candidates are returned. See execution_table step 5.

Visual Quiz - 3 Questions

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

A 10

B 15

C 17

D null

💡 Hint

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

At which step does the current node become null?

A Step 6

B Step 4

C Step 5

D Step 3

💡 Hint

Look at the 'Current Node' column to find when it changes to null.

If the key was 21 instead of 18, what would happen to the ceil candidate?

A It would remain null

B It would be updated to null

C It would be updated to 20

D It would remain 20

💡 Hint

Consider that 21 is greater than all nodes; ceil candidate updates when key < node value.

Concept Snapshot

Floor and Ceil in BST:
- Floor: largest value <= key
- Ceil: smallest value >= key
- Traverse from root:
  * If key < node, update ceil, go left
  * If key > node, update floor, go right
- Stop at leaf or exact match
- Return last floor and ceil candidates

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 the key is less than the node's value, update the ceil candidate to the current node's value and move left. If the key is greater, update the floor candidate and move right. Continue until you reach a leaf or find an exact match. The last updated floor and ceil candidates are the answers. This process ensures you find the closest values less than or equal to, and greater than or equal to, the key 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 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 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 smallest value
• Assuming floor is always the root

2. Which of the following is the correct Java method signature to find the ceil of a value in a BST node class?

easy

A. public int findCeil(Node root, int key)

B. int findCeil(Node root, int key) void

C. public void findCeil(Node root, int key) int

D. findCeil(Node root, int key) public int

Solution

1. Step 1: Recall Java method signature syntax

   In Java, a method signature includes access modifier, return type, method name, and parameters in parentheses.

2. Step 2: Check each option

   public int findCeil(Node root, int key) follows correct syntax: public int findCeil(Node root, int key). Others have incorrect order or missing return types.

3. Final Answer:

   public int findCeil(Node root, int key) -> Option A

4. Quick Check:

   Java method = access + return + name(params) [OK]

Hint: Java method: access + return type + name(params) [OK]

Common Mistakes:

• Placing return type after method name
• Omitting access modifier
• Using void when return type is int

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

       15
      /  \
    10    20
   /  \     \
  8   12    25

medium

A. Floor = 15, Ceil = 20

B. Floor = 12, Ceil = 15

C. Floor = 10, Ceil = 15

D. Floor = 12, Ceil = 20

Solution

1. Step 1: Find floor of 14 in BST

   Floor is greatest value ≤ 14. Values ≤14 are 8,10,12. Greatest is 12.

2. Step 2: Find ceil of 14 in BST

   Ceil is smallest value ≥ 14. Values ≥14 are 15,20,25. Smallest is 15.

3. Final Answer:

   Floor = 12, Ceil = 15 -> Option B

4. Quick Check:

   Floor ≤14 = 12, Ceil ≥14 = 15 [OK]

Hint: Floor ≤ key, Ceil ≥ key in BST [OK]

Common Mistakes:

• Choosing floor or ceil outside BST values
• Mixing floor and ceil values
• Ignoring BST property when searching

4. Consider this Java method to find floor in BST:

int floor(Node root, int key) {
  if (root == null) return -1;
  if (root.data == key) return root.data;
  if (root.data > key) return floor(root.left, key);
  int floorValue = floor(root.right, key);
  return (floorValue <= key && floorValue != -1) ? floorValue : root.data;
}

What is the bug in this code?

medium

A. It always searches left subtree

B. It does not check for null root

C. It returns -1 when key is found

D. It returns root.data even if floorValue is -1 and root.data > key

Solution

1. Step 1: Analyze the return condition when root.data > key

   If root.data > key, method searches left subtree correctly.

2. Step 2: Analyze return when root.data < key

   It gets floorValue from right subtree. If floorValue is -1 (no floor found), it returns root.data even if root.data > key, which is wrong.

3. Step 3: Identify bug

   Returning root.data without checking if root.data ≤ key causes incorrect floor when floorValue is -1.

4. Final Answer:

   It returns root.data even if floorValue is -1 and root.data > key -> Option D

5. Quick Check:

   Check root.data ≤ key before returning [OK]

Hint: Check root.data ≤ key before returning floor [OK]

Common Mistakes:

• Ignoring invalid floorValue -1
• Returning root.data without condition
• Not handling null root properly

5. You want to find both floor and ceil of a key in a BST efficiently. Which approach is best?

hard

A. Convert BST to sorted array, then binary search twice

B. Traverse BST twice: once for floor, once for ceil

C. Traverse BST once, updating floor and ceil during search

D. Use BFS traversal to find floor and ceil

Solution

1. Step 1: Understand BST properties for floor and ceil

   BST allows searching floor and ceil by comparing key with node values and moving left or right.

2. Step 2: Evaluate approaches

   Traversing once and updating floor and ceil during search is efficient (O(h)), better than traversing twice or converting to array.

3. Step 3: Choose best approach

   Traverse BST once, updating floor and ceil during search is best as it uses BST property and single traversal.

4. Final Answer:

   Traverse BST once, updating floor and ceil during search -> Option C

5. Quick Check:

   Single BST traversal updates floor & ceil [OK]

Hint: Update floor and ceil in one BST traversal [OK]

Common Mistakes:

• Doing two separate traversals
• Converting BST to array unnecessarily
• Using BFS which ignores BST order