Floor and Ceil in BST in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the floor of a given value in a Binary Search Tree (BST)?

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

beginner

What is the ceil of a given value in a Binary Search Tree (BST)?

The ceil of a value in a BST is the smallest value in the BST that is greater than or equal to the given value.

intermediate

In a BST, if the current node's value is greater than the target value, which subtree should you explore to find the floor?

You should explore the left subtree because values smaller than the current node might be closer to the target value but still less than or equal to it.

intermediate

In a BST, if the current node's value is less than the target value, which subtree should you explore to find the ceil?

You should explore the right subtree because values greater than the current node might be closer to the target value but still greater than or equal to it.

intermediate

What is the time complexity of finding floor or ceil in a balanced BST?

The time complexity is O(log n) because at each step you move down one level of the tree, reducing the search space by half.

What does the floor of a value in a BST represent?

A The smallest value greater than or equal to the target

B The greatest value less than or equal to the target

C The root value of the BST

D The smallest value in the BST

Floor is the greatest value in the BST that is less than or equal to the target value.

If the current node's value is equal to the target, what is the floor and ceil of the target in the BST?

A Floor and ceil are both the current node's value

B Floor is left child, ceil is right child

C Floor is the root, ceil is the leaf

D Floor and ceil do not exist

If the node's value equals the target, both floor and ceil are that value.

To find the ceil of a target value in a BST, if the current node's value is less than the target, where do you go next?

A Stop search

B Left subtree

C Return current node

D Right subtree

If current node's value is less than target, ceil must be in the right subtree.

What is the time complexity to find floor or ceil in a balanced BST?

A O(n)

B O(n log n)

C O(log n)

D O(1)

Balanced BST allows searching in O(log n) time by halving the search space each step.

If no value in the BST is less than or equal to the target, what is the floor value?

A No floor exists (null)

B The smallest value in the BST

C The largest value in the BST

D The root value

If no value ≤ target exists, floor does not exist and is null.

Explain how to find the floor of a given value in a BST step-by-step.

Think about how BST properties guide the search direction.

Describe the difference between floor and ceil in a BST and how their search paths differ.

Focus on how comparisons decide which subtree to explore.

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