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

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)
10	Up to 4 (if balanced)
100	Up to 7 (if balanced)
1000	Up 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?"