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

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func floorBST(root *Node, key int) *Node {
    var floorNode *Node
    current := root
    for current != nil {
        if current.val == key {
            return current
        } else if current.val > key {
            current = current.left
        } else {
            floorNode = current
            current = current.right
        }
    }
    return floorNode
}

This code finds the floor value (largest value less than or equal to key) in a BST by walking down the tree.

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 level of the tree, from root to leaf.

How Execution Grows With Input

As the BST grows, the search path length depends on the tree height.

Input Size (n)	Approx. Operations (steps down tree)
10	About 3 to 4
100	About 6 to 7
1000	About 9 to 10

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

Final Time Complexity

Time Complexity: O(h)

This means the time depends on the height of the BST, which is the longest path 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 height affects search time helps you explain why balanced trees are faster and shows you can analyze real code efficiently.

Self-Check

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