Bird
Raised Fist0
DSA C++programming~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 floorInBST(Node* root, int key) {
    int floorVal = -1;
    while (root) {
        if (root->data == key) return root->data;
        if (root->data > key) root = root->left;
        else {
            floorVal = root->data;
            root = root->right;
        }
    }
    return floorVal;
}

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 using a while loop.
  • How many times: At most once per tree level, moving left or right child each step.
How Execution Grows With Input

As the BST grows, the number of steps depends on the tree height.

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

Pattern observation: The steps grow slowly, roughly proportional to the tree height, not total nodes.

Final Time Complexity

Time Complexity: O(h)

This means the time depends on the height of the BST, which is the number of levels from root to leaf.

Common Mistake

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

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

Interview Connect

Understanding how BST properties help reduce search time is a key skill. It shows you can use data structure features to write efficient code.

Self-Check

"What if the BST is not balanced and becomes 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 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 average of all values in the BST

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 other options

    The smallest value in the BST greater than or equal to the given value describes ceil, while the remaining options are unrelated to floor concept.

  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 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(int val);
B. void ceilBST(Node root, int val);
C. Node* ceilBST(int val, Node* root);
D. int ceilBST(Node* root, int val);

Solution

  1. Step 1: Analyze function parameters and return type

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

  2. Step 2: Check each option

    int ceilBST(Node* root, int val); matches correct signature: returns int, takes Node* and int. Others have wrong parameter order, missing pointers, or wrong return type.

  3. Final Answer:

    int ceilBST(Node* root, int val); -> Option D

  4. Quick Check:

    Correct signature returns int and takes Node* root [OK]
Hint: Function needs root pointer and value, returns int [OK]
Common Mistakes:
  • Passing Node by value instead of pointer
  • Wrong parameter order
  • Incorrect return type
3. Given the BST below and the value 14, what is the ceil value? 
        10
       /  \
      5    15
          /  \
         12   20
medium
A. 12
B. 15
C. 20
D. 10

Solution

  1. Step 1: Locate value 14 in BST context

    14 is not in BST. We look for smallest value ≥ 14.

  2. Step 2: Check nodes greater than or equal to 14

    Nodes ≥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 node ≥ target [OK]
Common Mistakes:
  • Choosing 12 which is less than 14
  • Choosing 20 which is larger but not smallest ≥14
  • Confusing floor and ceil
4. Consider this buggy C++ code snippet to find floor in BST: 
int floorBST(Node* root, int val) {
  if (!root) return -1;
  if (root->data == val) return root->data;
  if (root->data > val) return floorBST(root->left, val);
  int floorRight = floorBST(root->right, val);
  return (floorRight != -1 && floorRight <= val) ? floorRight : root->data;
}
What is the bug?
medium
A. It always returns root->data without recursion
B. It does not check for null root
C. It returns root->data when floorRight is greater than val, which is incorrect
D. It returns -1 for all values

Solution

  1. Step 1: Understand the floor logic in code

    If root->data > val, search left subtree. Else search right subtree and compare.

  2. Step 2: Identify incorrect return condition

    The code returns root->data if floorRight > val. However, since floorRight is never > val (returns -1 or ≤ val), this never triggers, causing it to return -1 (when right subtree has no floor ≤ val) instead of root->data.

  3. Final Answer:

    It returns root->data when floorRight is greater than val, which is incorrect -> Option C

  4. Quick Check:

    Floor must be ≤ val, code returns invalid value [OK]
Hint: Floor must never exceed val; check return conditions [OK]
Common Mistakes:
  • Returning values greater than val as floor
  • Missing null checks
  • Ignoring recursion on left subtree
5. You have a BST with nodes: 8, 4, 12, 2, 6, 10, 14. You want to find both floor and ceil for value 7. Which pair is correct?
hard
A. Floor = 6, Ceil = 8
B. Floor = 8, Ceil = 6
C. Floor = 4, Ceil = 10
D. Floor = 7, Ceil = 7

Solution

  1. Step 1: Identify floor of 7 in BST

    Floor is greatest value ≤7. Values ≤7 are 2,4,6. Greatest is 6.

  2. Step 2: Identify ceil of 7 in BST

    Ceil is smallest value ≥7. Values ≥7 are 8,10,12,14. Smallest is 8.

  3. Final Answer:

    Floor = 6, Ceil = 8 -> Option A

  4. Quick Check:

    Floor ≤7 = 6, Ceil ≥7 = 8 [OK]
Hint: Floor ≤ val, Ceil ≥ val; pick closest values [OK]
Common Mistakes:
  • Swapping floor and ceil values
  • Assuming floor or ceil equals the value if not present
  • Choosing values not in BST
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