Floor and Ceil in BST in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floor and Ceil for a given key in BST

What is the output of the following Java code that finds floor and ceil values for key 15 in the BST?

DSA Java

class Node {
    int data;
    Node left, right;
    Node(int d) { data = d; left = right = null; }
}

public class BSTFloorCeil {
    Node root;

    int floor(Node root, int key) {
        int floorVal = -1;
        while (root != null) {
            if (root.data == key) return root.data;
            if (root.data > key) root = root.left;
            else {
                floorVal = root.data;
                root = root.right;
            }
        }
        return floorVal;
    }

    int ceil(Node root, int key) {
        int ceilVal = -1;
        while (root != null) {
            if (root.data == key) return root.data;
            if (root.data < key) root = root.right;
            else {
                ceilVal = root.data;
                root = root.left;
            }
        }
        return ceilVal;
    }

    public static void main(String[] args) {
        BSTFloorCeil tree = new BSTFloorCeil();
        tree.root = new Node(10);
        tree.root.left = new Node(5);
        tree.root.right = new Node(20);
        tree.root.left.left = new Node(3);
        tree.root.left.right = new Node(7);
        tree.root.right.left = new Node(15);
        tree.root.right.right = new Node(30);

        int key = 15;
        System.out.println("Floor: " + tree.floor(tree.root, key));
        System.out.println("Ceil: " + tree.ceil(tree.root, key));
    }
}

A {"Floor": 10, "Ceil": 20}

B {"Floor": 7, "Ceil": 15}

C {"Floor": 15, "Ceil": 15}

D {"Floor": 15, "Ceil": 20}

💡 Hint

Remember floor is the greatest value less than or equal to key, ceil is the smallest value greater than or equal to key.

Since 15 exists in the BST, both floor and ceil for key 15 are 15 itself.

❓ Predict Output

intermediate

Floor and Ceil for a key not present in BST

What is the output of floor and ceil for key 8 in the BST constructed below?

DSA Java

class Node {
    int data;
    Node left, right;
    Node(int d) { data = d; left = right = null; }
}

public class BSTFloorCeil {
    Node root;

    int floor(Node root, int key) {
        int floorVal = -1;
        while (root != null) {
            if (root.data == key) return root.data;
            if (root.data > key) root = root.left;
            else {
                floorVal = root.data;
                root = root.right;
            }
        }
        return floorVal;
    }

    int ceil(Node root, int key) {
        int ceilVal = -1;
        while (root != null) {
            if (root.data == key) return root.data;
            if (root.data < key) root = root.right;
            else {
                ceilVal = root.data;
                root = root.left;
            }
        }
        return ceilVal;
    }

    public static void main(String[] args) {
        BSTFloorCeil tree = new BSTFloorCeil();
        tree.root = new Node(10);
        tree.root.left = new Node(5);
        tree.root.right = new Node(20);
        tree.root.left.left = new Node(3);
        tree.root.left.right = new Node(7);
        tree.root.right.left = new Node(15);
        tree.root.right.right = new Node(30);

        int key = 8;
        System.out.println("Floor: " + tree.floor(tree.root, key));
        System.out.println("Ceil: " + tree.ceil(tree.root, key));
    }
}

A {"Floor": 7, "Ceil": 10}

B {"Floor": 8, "Ceil": 8}

C {"Floor": 10, "Ceil": 15}

D {"Floor": 5, "Ceil": 7}

💡 Hint

Floor is the greatest value less than or equal to key; ceil is the smallest value greater than or equal to key.

8 is not in the BST. The greatest value less than 8 is 7, and the smallest value greater than 8 is 10.

🔧 Debug

advanced

Identify the error in floor function implementation

What error will occur when running the floor function below for key 25 in the BST?

DSA Java

int floor(Node root, int key) {
    int floorVal = -1;
    while (root != null) {
        if (root.data == key) return root.data;
        if (root.data < key) {
            floorVal = root.data;
            root = root.right;
        } else {
            root = root.left;
        }
    }
    return floorVal;
}

// BST nodes: 10, 5, 20, 15, 30
// key = 25

A Runtime error due to null pointer

B Returns 30

C Returns -1

D Returns 20

💡 Hint

Floor is the greatest value less than or equal to key. Trace the path for key 25.

For key 25, floor is the greatest value <= 25. The function correctly updates floorVal to 20 and ends with 20.

🧠 Conceptual

advanced

Understanding floor and ceil when key is smaller than all nodes

If the key is smaller than all nodes in a BST, what will be the floor and ceil values returned by the functions?

A Floor: smallest node value, Ceil: -1

B Floor: -1, Ceil: smallest node value

C Floor: -1, Ceil: -1

D Floor: smallest node value, Ceil: smallest node value

💡 Hint

Floor is the greatest value less than or equal to key; if none exists, floor is -1.

If key is smaller than all nodes, floor does not exist (-1), ceil is the smallest node value.

🚀 Application

expert

Find floor and ceil for multiple keys efficiently

Given a BST and multiple keys, which approach is most efficient to find floor and ceil for all keys?

A Traverse BST once and store all nodes in sorted array, then use binary search for each key (O(m + n log m))

B Insert all keys into BST and then find floor and ceil for each key (O(n log (m+n)))

C For each key, run floor and ceil functions separately on BST (O(n log m) for n keys, m nodes)

D Use BFS traversal for each key to find floor and ceil (O(n*m))

💡 Hint

Think about preprocessing BST to speed up multiple queries.

Converting BST to sorted array allows binary search for floor and ceil in O(log m) per key, efficient for multiple queries.

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