Floor and Ceil in BST in DSA C# - Build from Scratch

Floor and Ceil in BST

📖 Scenario: You are working with a Binary Search Tree (BST) that stores integer values. You want to find two special values for a given number:Floor: The greatest value in the BST less than or equal to the given number.Ceil: The smallest value in the BST greater than or equal to the given number.This is useful in many real-world cases like searching for closest prices, dates, or scores.

🎯 Goal: Build a BST with given values, then write methods to find the floor and ceil values for a given target number.

📋 What You'll Learn

Create a BST by inserting nodes with exact values: 8, 4, 12, 2, 6, 10, 14

Create a variable target with the value 5

Write a method FindFloor that returns the floor value for target in the BST

Write a method FindCeil that returns the ceil value for target in the BST

Print the floor and ceil values exactly as: Floor: X, Ceil: Y

💡 Why This Matters

🌍 Real World

Finding floor and ceil values in sorted data structures is useful in price matching, scheduling, and recommendation systems where you want closest matches.

💼 Career

Understanding BST operations and searching techniques is important for software engineers working with databases, search engines, and real-time systems.

1

Create the BST with given nodes

Create a class Node with int data, Node left, and Node right. Then create a class BST with a Node root and a method Insert(int value) to add nodes. Insert these exact values in order: 8, 4, 12, 2, 6, 10, 14. Finally, create a BST object called tree and insert the values.

DSA C#

// Define Node and BST classes
// Create BST object tree
// Insert nodes 8, 4, 12, 2, 6, 10, 14
// Your code here

Hint

Define Node with data and two child pointers. Define BST with root and insert method. Insert nodes in the given order.

2

Create the target variable

Create an integer variable called target and set it to 5 inside the Main method after inserting nodes.

DSA C#

using System;

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

public class BST
{
    public Node root;

    public void Insert(int value)
    {
        root = InsertRec(root, value);
    }

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

class Program
{
    static void Main()
    {
        BST tree = new BST();
        tree.Insert(8);
        tree.Insert(4);
        tree.Insert(12);
        tree.Insert(2);
        tree.Insert(6);
        tree.Insert(10);
        tree.Insert(14);

        // Create target variable with value 5
        // Your code here
    }
}

Hint

Inside Main, write int target = 5; after inserting nodes.

3

Write methods to find Floor and Ceil

Add two methods inside the BST class: FindFloor(Node root, int target) and FindCeil(Node root, int target). Both return int? (nullable int). Implement FindFloor to return the greatest value less than or equal to target in the BST. Implement FindCeil to return the smallest value greater than or equal to target. Use recursion and BST properties. Call these methods from Main using tree.root and target, storing results in floor and ceil variables.

DSA C#

using System;

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

public class BST
{
    public Node root;

    public void Insert(int value)
    {
        root = InsertRec(root, value);
    }

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

    // Add FindFloor and FindCeil methods here
    // Your code here
}

class Program
{
    static void Main()
    {
        BST tree = new BST();
        tree.Insert(8);
        tree.Insert(4);
        tree.Insert(12);
        tree.Insert(2);
        tree.Insert(6);
        tree.Insert(10);
        tree.Insert(14);

        int target = 5;

        // Call FindFloor and FindCeil and store results
        // Your code here
    }
}

Hint

Use recursion and BST rules: if current node data is greater than target, go left for floor; if less, go right. Similar logic for ceil but reversed. Return null if no valid floor or ceil found.

4

Print the floor and ceil values

Print the floor and ceil values using Console.WriteLine exactly as: Floor: X, Ceil: Y where X is the floor value and Y is the ceil value. Use the variables floor and ceil.

DSA C#

using System;

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

public class BST
{
    public Node root;

    public void Insert(int value)
    {
        root = InsertRec(root, value);
    }

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

    public int? FindFloor(Node root, int target)
    {
        if (root == null) return null;
        if (root.data == target) return root.data;
        if (root.data > target) return FindFloor(root.left, target);
        int? floorValue = FindFloor(root.right, target);
        if (floorValue != null && floorValue = target) return ceilValue;
        else return root.data;
    }
}

class Program
{
    static void Main()
    {
        BST tree = new BST();
        tree.Insert(8);
        tree.Insert(4);
        tree.Insert(12);
        tree.Insert(2);
        tree.Insert(6);
        tree.Insert(10);
        tree.Insert(14);

        int target = 5;

        int? floor = tree.FindFloor(tree.root, target);
        int? ceil = tree.FindCeil(tree.root, target);

        // Print floor and ceil
        // Your code here
    }
}

Hint

Use Console.WriteLine($"Floor: {floor}, Ceil: {ceil}"); to print the results.

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