Floor and Ceil in BST in DSA Javascript - 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 value in a Binary Search Tree (BST).

How does the search time grow as the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function floorInBST(root, key) {
  let floor = null;
  while (root) {
    if (root.val === key) return root.val;
    if (root.val > key) root = root.left;
    else {
      floor = root.val;
      root = root.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: Traversing down the tree nodes one by one.
• How many times: At most once per tree level, moving left or right until a leaf or match is found.

How Execution Grows With Input

As the tree grows taller, the search path can get longer, but we only follow one path down.

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

Pattern observation: The number of steps grows slowly, roughly with the tree height, not the total nodes.

Final Time Complexity

Time Complexity: O(h)

This means the time depends on the tree height, which is the longest path from root to leaf.

Common Mistake

[X] Wrong: "Finding floor or ceil always takes time proportional to the total number of nodes."

[OK] Correct: We only follow one path down the tree, not all nodes, so time depends on height, not total nodes.

Interview Connect

Understanding how tree height affects search time helps you explain and optimize BST operations clearly in interviews.

Self-Check

"What if the BST is balanced versus completely unbalanced? How would the time complexity change?"