Floor and Ceil in BST in DSA Typescript - Deep Dive

Overview - Floor and Ceil in BST

What is it?

Floor and Ceil in a Binary Search Tree (BST) are two special values related to a given number. The floor is the greatest value in the BST that is less than or equal to the given number. The ceil is the smallest value in the BST that is greater than or equal to the given number. These help us quickly find close matches to a number in a sorted tree structure.

Why it matters

Without floor and ceil, finding the closest smaller or larger value to a number in a BST would require scanning many nodes, losing the efficiency BSTs provide. These operations are essential in many applications like range queries, nearest neighbor searches, and decision-making systems where approximate matches matter. They make BSTs more powerful and practical in real-world problems.

Where it fits

Before learning floor and ceil, you should understand what a Binary Search Tree is and how searching works in it. After mastering floor and ceil, you can explore more complex tree operations like range queries, predecessor and successor finding, and balanced BSTs like AVL or Red-Black trees.

Mental Model

Core Idea

Floor and ceil in a BST find the closest smaller-or-equal and larger-or-equal values to a target by smartly navigating the tree using BST properties.

Think of it like...

Imagine a bookshelf sorted by book height. If you want a book closest in height to a certain size, floor is the tallest book not taller than your size, and ceil is the shortest book not shorter than your size.

          [Root]
          /    \
      [Left]  [Right]

Floor search: go left if current node > target, else go right and update floor.
Ceil search: go right if current node < target, else go left and update ceil.

Build-Up - 7 Steps

1

Foundation

Understanding Binary Search Tree Basics

Concept: Learn what a BST is and how its structure helps in searching.

A BST is a tree where each node has at most two children. Left child nodes have smaller values, right child nodes have larger values. Searching starts at the root and moves left or right depending on comparison with the target value.

Result

You can find if a value exists in the BST efficiently by moving left or right at each step.

Understanding BST structure is key because floor and ceil rely on this ordered property to find closest values quickly.

2

Foundation

Basic Search Operation in BST

Concept: How to search for a value in BST by comparing and moving down the tree.

Start at root. If target equals node value, found it. If target < node value, go left. If target > node value, go right. Repeat until found or reach null.

Result

You can confirm presence or absence of a value in O(h) time, where h is tree height.

This search pattern is the foundation for floor and ceil, which modify it to track closest values instead of exact matches.

3

Intermediate

Finding Floor Value in BST

🤔Before reading on: do you think floor is found by always going left or right? Commit to your answer.

Concept: Floor is the greatest value less than or equal to target, found by moving right when possible and updating floor candidate.

Start at root. If node value equals target, floor is node value. If node value > target, go left (floor can't be here). If node value < target, update floor to node value and go right to find closer value. Repeat until null.

Result

You get the closest smaller or equal value to target in the BST or null if none exists.

Knowing when to update floor and when to move left or right is crucial to efficiently find the floor without scanning all nodes.

4

Intermediate

Finding Ceil Value in BST

🤔Before reading on: do you think ceil is found by always going left or right? Commit to your answer.

Concept: Ceil is the smallest value greater than or equal to target, found by moving left when possible and updating ceil candidate.

Start at root. If node value equals target, ceil is node value. If node value < target, go right (ceil can't be here). If node value > target, update ceil to node value and go left to find closer value. Repeat until null.

Result

You get the closest larger or equal value to target in the BST or null if none exists.

Understanding the opposite logic of floor helps find ceil efficiently by tracking candidates while moving through the tree.

5

Intermediate

Implementing Floor and Ceil in TypeScript

Concept: Translate the floor and ceil logic into runnable TypeScript code using BST node structure.

class TreeNode { val: number; left: TreeNode | null; right: TreeNode | null; constructor(val: number) { this.val = val; this.left = null; this.right = null; } } function floor(root: TreeNode | null, target: number): number | null { let floorVal: number | null = null; let node = root; while (node !== null) { if (node.val === target) return node.val; if (node.val > target) { node = node.left; } else { floorVal = node.val; node = node.right; } } return floorVal; } function ceil(root: TreeNode | null, target: number): number | null { let ceilVal: number | null = null; let node = root; while (node !== null) { if (node.val === target) return node.val; if (node.val < target) { node = node.right; } else { ceilVal = node.val; node = node.left; } } return ceilVal; }

Result

You can call floor(root, target) or ceil(root, target) to get closest values or null if none.

Implementing these functions concretely shows how the theory translates into efficient code using BST properties.

6

Advanced

Handling Edge Cases and Empty Trees

🤔Before reading on: do you think floor or ceil can return a value if the BST is empty? Commit to your answer.

Concept: Understand what happens when BST is empty or target is outside the BST value range.

If BST is empty (root is null), both floor and ceil return null because no values exist. If target is smaller than all nodes, floor returns null and ceil returns smallest node. If target is larger than all nodes, ceil returns null and floor returns largest node.

Result

Functions gracefully handle empty trees and out-of-range targets without errors.

Knowing these edge cases prevents bugs and ensures your code handles all inputs safely.

7

Expert

Optimizing Floor and Ceil in Balanced BSTs

🤔Before reading on: do you think balancing the BST affects floor and ceil performance? Commit to your answer.

Concept: Balanced BSTs keep height low, improving floor and ceil search times to O(log n). Unbalanced trees can degrade to O(n).

Balanced BSTs like AVL or Red-Black trees maintain height by rotations during insertions/deletions. Floor and ceil use the same logic but benefit from guaranteed low height, making searches faster and more predictable.

Result

Floor and ceil operations run efficiently even on large datasets due to balanced tree structure.

Understanding the impact of tree balance on floor and ceil performance helps in choosing the right BST variant for production systems.

Under the Hood

Floor and ceil work by traversing the BST from root, comparing target with current node. For floor, when node value is less than target, it becomes a candidate and search moves right to find a closer value. For ceil, when node value is greater than target, it becomes a candidate and search moves left. This selective traversal uses BST ordering to avoid unnecessary nodes.

Why designed this way?

BSTs are designed to keep values ordered so searching is efficient. Floor and ceil leverage this order to find closest values without scanning all nodes. Alternatives like linear search are slower. This design balances speed and simplicity.

Start at root
  ├─ if node.val == target: return node.val
  ├─ Floor search:
  │    ├─ if node.val > target: go left
  │    └─ else: update floor candidate, go right
  └─ Ceil search:
       ├─ if node.val < target: go right
       └─ else: update ceil candidate, go left

Myth Busters - 4 Common Misconceptions

Quick: Does floor always mean the immediate smaller value than target? Commit yes or no.

Common Belief: Floor is always the value just smaller than the target.

Reality: Floor can be equal to the target if the target exists in the BST.

Why it matters: Assuming floor is always smaller causes missing exact matches and incorrect results.

Quick: Can ceil be smaller than the target? Commit yes or no.

Common Belief: Ceil can be any value larger than the target, not necessarily the smallest larger or equal.

Reality: Ceil is specifically the smallest value greater than or equal to the target.

Why it matters: Misunderstanding ceil leads to wrong nearest value selection and bugs in range queries.

Quick: Is it necessary to traverse the entire BST to find floor or ceil? Commit yes or no.

Common Belief: You must check every node to find floor or ceil.

Reality: BST properties allow skipping large parts of the tree, so only O(h) nodes are visited.

Why it matters: Thinking full traversal is needed causes inefficient code and poor performance.

Quick: Does balancing the BST not affect floor and ceil search speed? Commit yes or no.

Common Belief: Balancing the BST does not impact floor and ceil performance.

Reality: Balanced BSTs guarantee O(log n) search time, unbalanced can degrade to O(n).

Why it matters: Ignoring balance can cause unexpected slowdowns in large datasets.

Expert Zone

1

Floor and ceil can be implemented recursively or iteratively; iterative avoids call stack overhead in large trees.

2

In augmented BSTs, floor and ceil can be combined with subtree size or rank information for advanced queries.

3

When duplicates exist, floor and ceil definitions depend on whether duplicates are allowed on left or right subtree, affecting implementation.

When NOT to use

If the data is unsorted or stored in a structure without order, floor and ceil in BST are not applicable. For dynamic datasets with frequent insertions/deletions, balanced BSTs or other data structures like skip lists or balanced interval trees may be better.

Production Patterns

Floor and ceil are used in database indexing to find range boundaries, in autocomplete systems to find closest matches, and in financial systems to find nearest price points. They are often combined with caching and balancing for performance.

Connections

Binary Search

Floor and ceil in BST build on the binary search principle of dividing search space by comparison.

Understanding binary search helps grasp how floor and ceil efficiently narrow down candidates in a sorted structure.

Interval Trees

Interval trees extend BSTs to handle ranges; floor and ceil concepts help find overlapping intervals.

Knowing floor and ceil aids in understanding how interval trees quickly locate relevant intervals.

Decision Making in Economics

Floor and ceil resemble choosing closest acceptable options under constraints, similar to price floors and ceilings in economics.

Recognizing this connection shows how algorithmic concepts mirror real-world decision boundaries and limits.

Common Pitfalls

#1 Returning floor or ceil without checking if BST is empty causes runtime errors.

Wrong approach:

function floor(root, target) {
let floorVal = null;
let node = root;
while (node.val !== null) { // error if node is null
if (node.val === target) return node.val;
if (node.val > target) node = node.left;
else {
floorVal = node.val;
node = node.right;
}
}
return floorVal;
}

Correct approach:

function floor(root, target) {
let floorVal = null;
let node = root;
while (node !== null) {
if (node.val === target) return node.val;
if (node.val > target) node = node.left;
else {
floorVal = node.val;
node = node.right;
}
}
return floorVal;
}

Root cause:

Not checking for null nodes before accessing properties leads to errors.

#2 Updating floor candidate when node value is greater than target.

Wrong approach:

if (node.val > target) {
floorVal = node.val; // wrong update
node = node.left;
}

Correct approach:

if (node.val > target) {
node = node.left; // do not update floor
}

Root cause:

Misunderstanding floor definition causes wrong candidate updates.

#3 Confusing floor and ceil logic by swapping left and right moves.

Wrong approach:

function ceil(root, target) {
let ceilVal = null;
let node = root;
while (node !== null) {
if (node.val === target) return node.val;
if (node.val > target) {
ceilVal = node.val;
node = node.right; // wrong direction
} else {
node = node.left; // wrong direction
}
}
return ceilVal;
}

Correct approach:

function ceil(root, target) {
let ceilVal = null;
let node = root;
while (node !== null) {
if (node.val === target) return node.val;
if (node.val < target) {
node = node.right;
} else {
ceilVal = node.val;
node = node.left;
}
}
return ceilVal;
}

Root cause:

Mixing up BST traversal directions for ceil leads to incorrect results.

Key Takeaways

Floor and ceil in BST find the closest smaller-or-equal and larger-or-equal values to a target efficiently by leveraging BST ordering.

They work by selectively moving left or right and updating candidate values without scanning the entire tree.

Handling edge cases like empty trees and out-of-range targets is essential for robust implementations.

Balanced BSTs improve floor and ceil search times by keeping tree height low.

Misunderstanding traversal directions or candidate updates causes common bugs; careful logic is key.