Bird
Raised Fist0
DSA Cprogramming~5 mins

Floor and Ceil in BST in DSA C - Time & Space Complexity

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Floor and Ceil in BST
O(h)
Understanding Time Complexity

We want to know how long it takes to find the floor or ceil of a value in a Binary Search Tree (BST).

Specifically, how the time grows as the tree gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


int floorBST(Node* root, int key) {
    int floor = -1;
    while (root) {
        if (root->data == key) return root->data;
        if (root->data > key) root = root->left;
        else {
            floor = root->data;
            root = root->right;
        }
    }
    return floor;
}

This code finds the floor value (largest value <= key) in a BST by traversing nodes.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: Traversing down the BST nodes one by one.
  • How many times: At most once per tree level, moving left or right each step.
How Execution Grows With Input

Each step moves down one level of the tree, so the number of steps depends on the tree height.

Input Size (n)Approx. Operations (steps)
10Up to 4 (if balanced)
100Up to 7 (if balanced)
1000Up to 10 (if balanced)

Pattern observation: Steps grow slowly with input size if tree is balanced, but can be as large as n if unbalanced.

Final Time Complexity

Time Complexity: O(h) where h is tree height

This means the time depends on how tall the tree is, not just how many nodes it has.

Common Mistake

[X] Wrong: "Finding floor or ceil always takes O(n) time because we might check every node."

[OK] Correct: The BST property lets us skip large parts of the tree, so we only follow one path down, not all nodes.

Interview Connect

Understanding this helps you explain how BSTs speed up searches compared to simple lists.

It shows you can use tree structure to find answers faster by skipping unnecessary parts.

Self-Check

"What if the BST is not balanced and looks like a linked list? How would the time complexity change?"

Practice

(1/5)
1. What does the floor of a value in a Binary Search Tree (BST) represent?
easy
A. The smallest value in the BST greater than or equal to the given value
B. The root value of the BST
C. The greatest value in the BST less than or equal to the given value
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 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 the smallest value
  • Assuming floor is always the root
2. Which of the following is the correct C function signature to find the ceil of a value in a BST node structure named Node?
easy
A. int ceilBST(Node* root, int key);
B. void ceilBST(Node root, int key);
C. Node* ceilBST(int key, Node* root);
D. int ceilBST(int key);

Solution

  1. Step 1: Analyze function parameters and return type

    The function should take a pointer to the root node and the key to find ceil for, returning an integer value.

  2. Step 2: Match with options

    int ceilBST(Node* root, int key); matches this: it takes Node* root and int key, returns int. Others have wrong parameter order, types, or return type.

  3. Final Answer:

    int ceilBST(Node* root, int key); -> Option A

  4. Quick Check:

    Correct signature: pointer root, key, returns int [OK]
Hint: Function takes root pointer and key, returns int [OK]
Common Mistakes:
  • Passing root by value instead of pointer
  • Wrong parameter order
  • Returning Node* instead of int
3. Given the BST below and the key = 14, what is the output of the ceil function? 

        10
       /  \
      5    15
          /  \
         12   20
medium
A. -1
B. 15
C. 12
D. 20

Solution

  1. Step 1: Understand ceil definition and traverse BST

    Ceil is smallest value ≥ key. Starting at root 10, since 14 > 10, move right to 15. 15 ≥ 14, so candidate ceil is 15. Check left subtree of 15 (12) which is < 14, so ignore.

  2. Step 2: Confirm smallest candidate

    15 is the smallest node ≥ 14. 20 is larger but not smaller than 15, so 15 is ceil.

  3. Final Answer:

    15 -> Option B

  4. Quick Check:

    Ceil(14) = 15 [OK]
Hint: Ceil is smallest node ≥ key, check right subtree carefully [OK]
Common Mistakes:
  • Choosing 20 instead of 15
  • Choosing 12 which is < 14
  • Returning -1 when ceil exists
4. Consider the following buggy C code snippet to find floor in BST. What is the main error? 

int floorBST(Node* root, int key) {
    if (!root) return -1;
    if (root->data == key) return root->data;
    if (root->data > key) return floorBST(root->left, key);
    int floorValue = floorBST(root->right, key);
    if (floorValue <= key && floorValue != -1) return floorValue;
    else return root->data;
}
medium
A. It returns root->data even if floorValue is -1
B. It does not check for NULL root
C. It returns -1 when key is found
D. It incorrectly searches left subtree when root->data < key

Solution

  1. Step 1: Analyze return conditions

    If floorValue is -1 (meaning no floor found in right subtree), the code returns root->data without checking if root->data ≤ key, which can be incorrect.

  2. Step 2: Identify the error

    The code should check if root->data ≤ key before returning it; otherwise, it may return a value greater than key, violating floor definition.

  3. Final Answer:

    It returns root->data even if floorValue is -1 -> Option A

  4. Quick Check:

    Missing check before returning root->data causes wrong floor [OK]
Hint: Check root->data ≤ key before returning it [OK]
Common Mistakes:
  • Ignoring floorValue == -1 case
  • Returning wrong subtree
  • Not handling NULL root
5. You have a BST with nodes: 8, 4, 12, 2, 6, 10, 14. You want to find the floor and ceil of 5. Which pair is correct?
hard
A. Floor = 5, Ceil = 5
B. Floor = 6, Ceil = 4
C. Floor = 2, Ceil = 8
D. Floor = 4, Ceil = 6

Solution

  1. Step 1: Identify floor of 5 in BST

    Floor is greatest value ≤ 5. Nodes ≤ 5 are 2 and 4. Greatest is 4.

  2. Step 2: Identify ceil of 5 in BST

    Ceil is smallest value ≥ 5. Nodes ≥ 5 are 6, 8, 10, 12, 14. Smallest is 6.

  3. Final Answer:

    Floor = 4, Ceil = 6 -> Option D

  4. Quick Check:

    Floor(5)=4, Ceil(5)=6 [OK]
Hint: Floor ≤ key, ceil ≥ key; pick closest values [OK]
Common Mistakes:
  • Swapping floor and ceil values
  • Assuming floor or ceil equals key if not present
  • Choosing wrong closest values
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard