Floor and Ceil in BST in DSA C# - Execution Trace

Concept Flow - Floor and Ceil in BST

Start at root

↓

Compare target with current node

↓

Floor = Ceil = node value

→Done

↓

Go to left subtree

↓

Go to right subtree

↓

Update floor or ceil accordingly

↓

Repeat until leaf or found exact match

Start at the root and compare the target with current node value. Move left if target is smaller, right if larger, updating floor or ceil candidates until you find exact match or reach leaf.

Execution Sample

DSA C#

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

int Floor(Node root, int target) {
  // returns floor value or -1 if none
  int floor = -1;
  Node current = root;
  while (current != null) {
    if (current.val == target) {
      return current.val;
    } else if (current.val > target) {
      current = current.left;
    } else {
      floor = current.val;
      current = current.right;
    }
  }
  return floor;
}

Find floor value in BST for given target by traversing tree and updating candidate floor.

Execution Table

Step	Operation	Current Node	Floor Candidate	Ceil Candidate	Visual State
1	Start at root	20	null	null	20 / \ 10 30
2	Compare target=25 with 20	20	20	null	20 / \ 10 30
3	Target > 20, go right	30	20	null	20 / \ 10 30
4	Compare target=25 with 30	30	20	30	20 / \ 10 30
5	Target < 30, go left	null	20	30	20 / \ 10 30
6	Reached leaf, stop	null	20	30	20 / \ 10 30

💡 Reached leaf node with no exact match; floor=20, ceil=30

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6
Current Node	20	20	30	null
Floor Candidate	null	20	20	20
Ceil Candidate	null	null	30	30

Key Moments - 3 Insights

Why do we update floor candidate only when target > current node value?

Because floor is the greatest value less than or equal to target. When target > node value, node value can be a floor candidate. See execution_table step 2 and 3.

Why do we update ceil candidate only when target < current node value?

Because ceil is the smallest value greater than or equal to target. When target < node value, node value can be a ceil candidate. See execution_table step 4.

What happens if target equals a node value?

Floor and ceil both equal that node value, and search stops immediately. This is shown in concept_flow but not in this example.

Visual Quiz - 3 Questions

Look at the execution_table, what is the floor candidate after step 4?

A null

B 30

C 20

D 25

💡 Hint

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

At which step does the algorithm decide to go left from node 30?

A Step 2

B Step 5

C Step 3

D Step 4

💡 Hint

Look at the 'Operation' and 'Current Node' columns in execution_table.

If the target was 10, what would be the floor candidate after starting at root?

A null

B 20

C 10

D 30

💡 Hint

Floor candidate updates only when target > current node value; see variable_tracker and key_moments.

Concept Snapshot

Floor and Ceil in BST:
- Floor: greatest value ≤ target
- Ceil: smallest value ≥ target
- Traverse from root:
  * If target == node, floor=ceil=node
  * If target < node, go left, update ceil
  * If target > node, go right, update floor
- Stop at leaf or exact match

Full Transcript

To find floor and ceil in a Binary Search Tree (BST), start at the root node. Compare the target value with the current node's value. If they are equal, both floor and ceil are that value. If the target is less than the node's value, move to the left subtree and update the ceil candidate to the current node's value. If the target is greater, move to the right subtree and update the floor candidate to the current node's value. Continue this process until you reach a leaf node or find an exact match. The floor is the greatest value less than or equal to the target, and the ceil is the smallest value greater than or equal to the target. This method efficiently uses BST properties to find floor and ceil without searching the entire tree.

Practice

1. What does the floor of a value in a Binary Search Tree (BST) represent?

easy

A. The smallest value in the BST less than the given value

B. The smallest value in the BST greater than or equal to the given value

C. The greatest value in the BST less than or equal to the given value

D. The root node value of the BST

Solution

1. Step 1: Understand the definition of floor in BST

   The floor of a value in BST is the largest value 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 ceil or unrelated concepts.

3. Final Answer:

   The greatest value in the BST less than or equal to the given value -> Option C

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 always smaller than the value
• Assuming floor is the root value

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

easy

A. public int FindCeil(int key)

B. int FindCeil(int key, Node root)

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

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

Solution

1. Step 1: Understand method signature requirements

   The method should be public, return an int (the ceil value), and accept the BST root node and the key to find ceil for.

2. Step 2: Match with options

   public int FindCeil(Node root, int key) matches this: public int FindCeil(Node root, int key). int FindCeil(int key, Node root) has wrong parameter order, C returns void, D misses root parameter.

3. Final Answer:

   public int FindCeil(Node root, int key) -> Option D

4. Quick Check:

   Correct signature returns int and takes root, key [OK]

Hint: Method returns int, takes root and key in order [OK]

Common Mistakes:

• Wrong parameter order
• Using void return type
• Missing root parameter

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

        10
       /  \
      5    15
          /  \
         12   20

medium

A. 12

B. 15

C. 20

D. 10

Solution

1. Step 1: Understand ceil definition and BST structure

   Ceil is the smallest value greater than or equal to 14. The BST nodes are 10, 5, 15, 12, 20.

2. Step 2: Find values ≥ 14 and pick smallest

   Values ≥ 14 are 15 and 20. The smallest among these is 15.

3. Final Answer:

   15 -> Option B

4. Quick Check:

   Ceil(14) = 15 [OK]

Hint: Ceil is smallest ≥ key in BST [OK]

Common Mistakes:

• Choosing 12 which is less than 14
• Choosing 20 which is greater but not smallest
• Confusing ceil with floor

4. Consider this buggy C# code snippet to find floor in BST:

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

What is the main issue causing incorrect floor results?

medium

A. The condition to check floorVal is incorrect and may return wrong value

B. The base case returns -1 which may be confused with valid floor

C. The function does not handle the case when root.val < key

D. The function does not recurse on left subtree when root.val < key

Solution

1. Step 1: Analyze the floorVal condition

   The code checks if floorVal ≤ key and floorVal != -1 to decide return value. But floorVal could be less than root.val and still valid floor.

2. Step 2: Identify the incorrect logic

   The condition should check if floorVal is greater than root.val to pick the better floor, but it doesn't, causing wrong floor return.

3. Final Answer:

   The condition to check floorVal is incorrect and may return wrong value -> Option A

4. Quick Check:

   Incorrect floorVal check causes wrong floor [OK]

Hint: Check floorVal against root.val, not just key [OK]

Common Mistakes:

• Ignoring comparison with root.val
• Returning -1 as valid floor
• 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 to implement in C#?

hard

A. Traverse the BST once, updating floor and ceil candidates during traversal

B. Perform two separate traversals: one for floor and one for ceil

C. Convert BST to sorted array, then use binary search twice

D. Use BFS traversal to find floor and ceil simultaneously

Solution

1. Step 1: Consider efficiency of approaches

   Two separate traversals or converting to array add extra time or space. BFS is not suitable for ordered search.

2. Step 2: Single traversal updating floor and ceil

   During one BST traversal, compare node values with key to update floor (largest ≤ key) and ceil (smallest ≥ key) efficiently.

3. Final Answer:

   Traverse the BST once, updating floor and ceil candidates during traversal -> Option A

4. Quick Check:

   Single traversal updates floor and ceil efficiently [OK]

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

Common Mistakes:

• Doing two separate traversals wasting time
• Using BFS which ignores BST order
• Converting BST to array wastes space