Floor and Ceil in BST in DSA Java

Mental Model

Floor is the biggest value smaller or equal to target; ceil is the smallest value bigger or equal to target in the BST.

Analogy: Imagine a ladder with steps labeled by numbers. Floor is the highest step you can stand on without going above your target height. Ceil is the lowest step you must step on to reach or go above the target height.

       8
      / \
     4   12
    / \   / \
   2   6 10  14

Dry Run Walkthrough

Input: BST: 8->4->12->2->6->10->14, find floor and ceil of 5

Goal: Find the floor (largest ≤5) and ceil (smallest ≥5) values in the BST

Step 1: Start at root node 8, compare 5 with 8

Current node: 8

Why: We start from root to find floor and ceil by comparing target with node values

Step 2: Since 5 < 8, move to left child 4 for ceil candidate

Current node: 4

Why: Ceil must be ≥5, so 8 is a ceil candidate, but smaller values might be closer

Step 3: Since 5 > 4, record floor candidate as 4 and move to right child 6 for better floor

Current node: 6, floor candidate: 4

Why: Floor must be ≤5, 4 fits, but maybe 6 or its left child fits better

Step 4: Since 5 < 6, move to left child which is null, update ceil candidate to 6

Current node: null, floor candidate: 4, ceil candidate: 6

Why: 6 is ≥5, so it is a ceil candidate; no left child means no smaller ceil

Result:

Floor: 4, Ceil: 6

Annotated Code

DSA Java

class Node {
    int val;
    Node left, right;
    Node(int val) { this.val = val; }
}

public class FloorCeilBST {
    public static int floor(Node root, int target) {
        int floor = -1;
        Node curr = root;
        while (curr != null) {
            if (curr.val == target) {
                return curr.val; // exact match is floor
            } else if (curr.val > target) {
                curr = curr.left; // move left to find smaller or equal
            } else {
                floor = curr.val; // update floor candidate
                curr = curr.right; // try to find closer floor
            }
        }
        return floor;
    }

    public static int ceil(Node root, int target) {
        int ceil = -1;
        Node curr = root;
        while (curr != null) {
            if (curr.val == target) {
                return curr.val; // exact match is ceil
            } else if (curr.val < target) {
                curr = curr.right; // move right to find bigger or equal
            } else {
                ceil = curr.val; // update ceil candidate
                curr = curr.left; // try to find closer ceil
            }
        }
        return ceil;
    }

    public static void main(String[] args) {
        Node root = new Node(8);
        root.left = new Node(4);
        root.right = new Node(12);
        root.left.left = new Node(2);
        root.left.right = new Node(6);
        root.right.left = new Node(10);
        root.right.right = new Node(14);

        int target = 5;
        System.out.println("Floor: " + floor(root, target));
        System.out.println("Ceil: " + ceil(root, target));
    }
}

while (curr != null) {

Traverse nodes until no more candidates

if (curr.val == target) { return curr.val; }

Exact match found, return immediately

else if (curr.val > target) { curr = curr.left; }

Move left to find smaller or equal values for floor

else { floor = curr.val; curr = curr.right; }

Update floor candidate and move right to find closer floor

else if (curr.val < target) { curr = curr.right; }

Move right to find bigger or equal values for ceil

else { ceil = curr.val; curr = curr.left; }

Update ceil candidate and move left to find closer ceil

Output

Floor: 4

Ceil: 6

Complexity Analysis

Time: O(h) because we traverse from root down to leaf where h is tree height

Space: O(1) because we use only a few variables, no extra data structures

vs Alternative: Compared to scanning all nodes O(n), this uses BST property to reduce to O(h)

Edge Cases

target smaller than all nodes

floor returns -1 (no floor), ceil returns smallest node

DSA Java

int floor = -1;

target larger than all nodes

floor returns largest node, ceil returns -1 (no ceil)

DSA Java

int ceil = -1;

target equals a node value

floor and ceil both return that node value immediately

DSA Java

if (curr.val == target) { return curr.val; }

When to Use This Pattern

When asked to find closest smaller or larger values in a BST, use floor and ceil patterns leveraging BST ordering to search efficiently.

Common Mistakes

Mistake: Not updating floor or ceil candidate before moving right or left
Fix: Always update candidate before moving to subtree that might have closer values

Mistake: Returning -1 without checking if target equals a node value
Fix: Check for exact match first and return immediately

Summary

Find the closest smaller or equal (floor) and closest larger or equal (ceil) values to a target in a BST.

Use when you need nearest bounds for a value in a sorted tree structure.

The key is to move left or right based on comparison and update candidates along the way.

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