Bird
Raised Fist0
DSA Typescriptprogramming~5 mins

Floor and Ceil in BST in DSA Typescript - 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.


function floorInBST(root: TreeNode | null, key: number): number | null {
  let floor: number | null = null;
  let current = root;
  while (current) {
    if (current.val === key) return current.val;
    if (current.val > key) current = current.left;
    else {
      floor = current.val;
      current = current.right;
    }
  }
  return floor;
}

This code finds the floor value (largest value less than or equal to key) in a BST by moving left or right.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: The while loop that moves down the tree nodes.
  • How many times: At most once per tree level, moving down from root to leaf.
How Execution Grows With Input

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

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

Pattern observation: The steps grow slowly, roughly with the tree height, which is about log of n if balanced.

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, showing your grasp of efficient data structures.

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 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 in BST is the greatest value 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, not floor. Options C and D 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 TypeScript function signatures correctly represents a function to find the ceil in a BST?
easy
A. function findCeil(key: number, root: TreeNode): number
B. function findCeil(root: TreeNode | null, key: number): number | null
C. function findCeil(root: TreeNode, key: string): number
D. function findCeil(root: TreeNode | null): number

Solution

  1. Step 1: Check parameter order and types

    Function should accept root node (possibly null) and a key number to find ceil for.

  2. Step 2: Validate return type

    Return type should be number or null if no ceil found. function findCeil(root: TreeNode | null, key: number): number | null matches this.

  3. Final Answer:

    function findCeil(root: TreeNode | null, key: number): number | null -> Option B

  4. Quick Check:

    Correct params and return type [OK]
Hint: Root first, key second, return number or null [OK]
Common Mistakes:
  • Swapping parameter order
  • Using wrong parameter types
  • Missing null in root type
3. Given the BST below and key = 14, what is the ceil value? 
       10
      /  \
     5    15
         /  \
        12   20
medium
A. 12
B. 20
C. 15
D. null

Solution

  1. Step 1: Locate key 14 in BST or nearest nodes

    14 is not in BST. Check nodes greater than or equal to 14: 15 and 20.

  2. Step 2: Find smallest node ≥ 14

    Between 15 and 20, 15 is smaller and ≥ 14, so ceil is 15.

  3. Final Answer:

    15 -> Option C

  4. Quick Check:

    Ceil = smallest ≥ 14 is 15 [OK]
Hint: Ceil is smallest value ≥ key in BST [OK]
Common Mistakes:
  • Choosing 12 which is less than 14
  • Choosing 20 which is larger but not smallest ≥ 14
  • Returning null when ceil exists
4. Consider this TypeScript function to find floor in BST: 
function findFloor(root: TreeNode | null, key: number): number | null {
  if (!root) return null;
  if (root.val === key) return root.val;
  const floorRight = findFloor(root.right, key);
  return floorRight !== null ? floorRight : root.val;
}
What is the bug in this code?
medium
A. It returns root.val even if floorRight is null and root.val > key
B. It does not check for null root
C. It returns key instead of floor value
D. It incorrectly calls findFloor on root.left when root.val < key

Solution

  1. Step 1: Identify missing logic for root.val > key

    The code does not recurse into the left subtree when root.val > key. Instead, it always computes floorRight from the right subtree.

  2. Step 2: Trace buggy return

    When root.val > key and right subtree yields null for floorRight (common case), it returns root.val which exceeds key, violating floor definition.

  3. Final Answer:

    It returns root.val even if floorRight is null and root.val > key -> Option A

  4. Quick Check:

    Missing left recursion on root.val > key [OK]
Hint: Check return when right subtree floor is null [OK]
Common Mistakes:
  • Ignoring null checks
  • Confusing left and right subtree calls
  • Assuming root.val always valid floor
5. You have a BST with values [8, 4, 12, 2, 6, 10, 14]. You want to find the floor and ceil of 5. Which pair is correct?
medium
A. Floor = 2, Ceil = 8
B. Floor = 6, Ceil = 4
C. Floor = 5, Ceil = 5
D. Floor = 4, Ceil = 6

Solution

  1. Step 1: Identify floor of 5 in BST

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

  2. Step 2: Identify ceil of 5 in BST

    Ceil is smallest value ≥ 5. Values ≥ 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 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