Floor and Ceil in BST in DSA Java - Build from Scratch

Floor and Ceil in BST

📖 Scenario: You are working with a phone book application that stores contact numbers in a Binary Search Tree (BST). You want to find the closest existing contact number that is less than or equal to a given number (floor), and the closest existing contact number that is greater than or equal to the given number (ceil).

🎯 Goal: Build a Java program that creates a BST with given contact numbers, sets a target number, finds the floor and ceil values in the BST for that target, and prints them.

📋 What You'll Learn

Create a BST by inserting given integers in the exact order

Create an integer variable for the target number

Implement methods to find floor and ceil values in the BST for the target

Print the floor and ceil values found

💡 Why This Matters

🌍 Real World

Finding floor and ceil values in a BST is useful in applications like phone book lookups, price matching, and range queries where you want the closest existing value to a target.

💼 Career

Understanding BST operations and floor/ceil logic is important for software engineers working on search algorithms, database indexing, and real-time data retrieval systems.

1

Create BST with given contact numbers

Create a class Node with integer data, and Node references left and right. Then create a class BST with a Node variable root. Insert the integers 20, 10, 30, 5, 15, 25, and 35 into the BST in this exact order using an insert method.

DSA Java

// Define Node class
// Define BST class with root
// Insert 20, 10, 30, 5, 15, 25, 35 into BST
// Your code here

Hint

Start by defining the Node class with data and child references. Then create the BST class with a root node and an insert method that adds nodes in the correct position.

2

Set the target number to find floor and ceil

Inside the main method, create an integer variable called target and set it to 28.

DSA Java

class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
        left = right = null;
    }
}

class BST {
    Node root;

    void insert(int data) {
        root = insertRec(root, data);
    }

    Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        if (data  root.data) {
            root.right = insertRec(root.right, data);
        }
        return root;
    }

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(20);
        tree.insert(10);
        tree.insert(30);
        tree.insert(5);
        tree.insert(15);
        tree.insert(25);
        tree.insert(35);
        // Create target variable and set to 28
        // Your code here
    }
}

Hint

Inside the main method, declare an integer variable named target and assign it the value 28.

3

Implement methods to find floor and ceil in BST

Add two methods in the BST class: int floor(Node root, int target) and int ceil(Node root, int target). Both methods should return the floor and ceil values for the target in the BST. Use the BST property to traverse nodes and find the correct values.

DSA Java

class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
        left = right = null;
    }
}

class BST {
    Node root;

    void insert(int data) {
        root = insertRec(root, data);
    }

    Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        if (data  root.data) {
            root.right = insertRec(root.right, data);
        }
        return root;
    }

    // Add floor method here
    // Add ceil method here

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(20);
        tree.insert(10);
        tree.insert(30);
        tree.insert(5);
        tree.insert(15);
        tree.insert(25);
        tree.insert(35);
        int target = 28;
        // Your code here
    }
}

Hint

Use a loop to traverse the BST starting from root. For floor, move left if current node data is greater than target, else update floor and move right. For ceil, move right if current node data is less than target, else update ceil and move left.

4

Print the floor and ceil values for the target

In the main method, call the floor and ceil methods on the tree object with tree.root and target. Store the results in variables floorValue and ceilValue. Then print these values exactly as: Floor: <floorValue> and Ceil: <ceilValue>.

DSA Java

class Node {
    int data;
    Node left, right;

    Node(int data) {
        this.data = data;
        left = right = null;
    }
}

class BST {
    Node root;

    void insert(int data) {
        root = insertRec(root, data);
    }

    Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        if (data  root.data) {
            root.right = insertRec(root.right, data);
        }
        return root;
    }

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

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

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(20);
        tree.insert(10);
        tree.insert(30);
        tree.insert(5);
        tree.insert(15);
        tree.insert(25);
        tree.insert(35);
        int target = 28;
        // Call floor and ceil methods and print results
        // Your code here
    }
}

Hint

Call floor and ceil with tree.root and target. Store results in floorValue and ceilValue. Print them with System.out.println exactly as shown.

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