Floor and Ceil in BST in DSA Javascript - Deep Dive

Overview - Floor and Ceil in BST

What is it?

Floor and Ceil in a Binary Search Tree (BST) are two 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 find closest matches quickly in sorted data stored as a BST.

Why it matters

Without floor and ceil operations, finding closest smaller or larger values in sorted data would require scanning all elements, which is slow. Floor and ceil let us quickly find these values using the BST's structure, saving time and making programs faster and more efficient. This is useful in many real-world tasks like searching, scheduling, and decision making.

Where it fits

Before learning floor and ceil in BST, you should understand what a Binary Search Tree is and how it organizes data. After this, you can explore related topics like range queries, nearest neighbor search, and balanced BSTs like AVL or Red-Black trees for faster operations.

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 walking the tree using its sorted order.

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.

          [BST Node]
          /       \
    [Left Subtree] [Right Subtree]

Floor search: move left if node value > target, else record node and move right.
Ceil search: move right if node value < target, else record node and move left.

Build-Up - 7 Steps

1

Foundation

Understanding Binary Search Tree Basics

Concept: Learn what a BST is and how it stores data in a sorted way.

A Binary Search Tree is a tree where each node has up to two children. The left child has a smaller value, and the right child has a larger value than the node. This property helps us find values quickly by deciding to go left or right at each step.

Result

You can find if a value exists in the BST by comparing and moving left or right, not checking every node.

Understanding BST structure is key because floor and ceil rely on this sorted order to find closest values efficiently.

2

Foundation

What Are Floor and Ceil Values?

Concept: Define floor and ceil in simple terms related to numbers.

Floor of a number is the biggest number less than or equal to it. Ceil is the smallest number greater than or equal to it. For example, floor of 7 in [2,5,8,10] is 5, ceil is 8.

Result

You know what floor and ceil mean for any list of numbers.

Grasping floor and ceil as closest smaller or larger values helps connect to their use in BST.

3

Intermediate

Finding Floor in a BST

🤔Before reading on: do you think floor search moves left or right when current node value is less than target? Commit to your answer.

Concept: Floor search uses BST property to find the closest smaller or equal value by moving left or right.

Start at root. If node value equals target, floor is found. If node value > target, move left to find smaller values. If node value < target, record node as potential floor and move right to find closer values.

Result

Floor value found or null if none exists.

Knowing when to move left or right and when to record a candidate is crucial for efficient floor search.

4

Intermediate

Finding Ceil in a BST

🤔Before reading on: do you think ceil search moves left or right when current node value is greater than target? Commit to your answer.

Concept: Ceil search finds the closest larger or equal value by navigating the BST similarly but in reverse direction logic.

Start at root. If node value equals target, ceil is found. If node value < target, move right to find larger values. If node value > target, record node as potential ceil and move left to find closer values.

Result

Ceil value found or null if none exists.

Understanding the mirror logic of ceil compared to floor helps avoid confusion and errors.

5

Intermediate

Implementing Floor and Ceil in JavaScript

Concept: Write code to perform floor and ceil searches in a BST using recursion.

function floorBST(root, target) { if (!root) return null; if (root.val === target) return root.val; if (root.val > target) return floorBST(root.left, target); const floorRight = floorBST(root.right, target); return floorRight !== null ? floorRight : root.val; } function ceilBST(root, target) { if (!root) return null; if (root.val === target) return root.val; if (root.val < target) return ceilBST(root.right, target); const ceilLeft = ceilBST(root.left, target); return ceilLeft !== null ? ceilLeft : root.val; }

Result

Functions return correct floor or ceil values or null if none.

Seeing the code clarifies how recursion and BST properties combine to find floor and ceil efficiently.

6

Advanced

Handling Edge Cases and Null Results

🤔Before reading on: if target is smaller than all BST values, what should floor return? Commit to your answer.

Concept: Understand what happens when floor or ceil does not exist in the BST and how to handle it.

If target is smaller than all nodes, floor is null because no smaller or equal value exists. Similarly, if target is larger than all nodes, ceil is null. Code must return null in these cases to signal no valid floor or ceil.

Result

Robust floor and ceil functions that handle all inputs without errors.

Knowing these edge cases prevents bugs and incorrect assumptions in real applications.

7

Expert

Optimizing Floor and Ceil with Iterative Search

🤔Before reading on: do you think iterative or recursive approach uses less memory for floor and ceil? Commit to your answer.

Concept: Use iteration instead of recursion to reduce memory use and improve performance in large BSTs.

function floorBSTIter(root, target) { let floor = null; let node = root; while (node) { if (node.val === target) return node.val; if (node.val > target) node = node.left; else { floor = node.val; node = node.right; } } return floor; } function ceilBSTIter(root, target) { let ceil = null; let node = root; while (node) { if (node.val === target) return node.val; if (node.val < target) node = node.right; else { ceil = node.val; node = node.left; } } return ceil; }

Result

Iterative functions find floor and ceil without recursion stack overhead.

Understanding iterative search helps write more efficient code for large or deep BSTs where recursion may cause stack overflow.

Under the Hood

Floor and ceil searches use the BST's sorted property to prune search paths. At each node, the algorithm decides to go left or right based on comparison with the target. It keeps track of the best candidate found so far. This avoids visiting all nodes, reducing time complexity to O(h), where h is tree height.

Why designed this way?

BSTs are designed to keep data sorted for fast search. Floor and ceil operations leverage this by narrowing down candidates quickly. Alternatives like scanning all nodes would be slower. Recursive and iterative methods reflect tradeoffs between simplicity and memory use.

Start at root
  ↓
Compare node.val with target
  ├─ If equal -> return node.val
  ├─ For floor:
  │    ├─ If node.val > target -> go left
  │    └─ Else record node.val, go right
  └─ For ceil:
       ├─ If node.val < target -> go right
       └─ Else record node.val, go left

Myth Busters - 3 Common Misconceptions

Quick: Does floor always equal the target if it exists in BST? Commit yes or no.

Common Belief: Floor is always the target value if it exists in the BST.

Reality: Floor equals the target only if the target is present; otherwise, it is the greatest smaller value.

Why it matters: Assuming floor always equals target causes incorrect results when target is missing, leading to wrong decisions.

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

Common Belief: Ceil can be smaller than the target if no exact match exists.

Reality: Ceil is always greater than or equal to the target; it cannot be smaller.

Why it matters: Misunderstanding ceil leads to logic errors in algorithms relying on correct bounds.

Quick: Is recursion always better than iteration for floor and ceil? Commit yes or no.

Common Belief: Recursion is always the best way to implement floor and ceil in BST.

Reality: Iteration can be more efficient and safer for large trees by avoiding stack overflow.

Why it matters: Ignoring iterative methods can cause crashes or performance issues in real systems.

Expert Zone

1

Floor and ceil results depend heavily on tree balance; unbalanced BSTs degrade performance to linear time.

2

When multiple nodes have the same value, floor and ceil return that value immediately, but duplicates can complicate logic in some BST variants.

3

In augmented BSTs, floor and ceil can be combined with other queries like rank or count for advanced data retrieval.

When NOT to use

If the BST is highly unbalanced or data changes frequently, balanced trees like AVL or Red-Black trees or other data structures like B-Trees or skip lists may be better for floor and ceil operations.

Production Patterns

Floor and ceil are used in database indexing to find range boundaries, in scheduling systems to find closest time slots, and in autocomplete features to find nearest matches efficiently.

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 BST floor and ceil narrow down candidates quickly.

Interval Trees

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

Knowing floor and ceil aids understanding how interval trees locate closest or overlapping intervals efficiently.

Real Number Line Approximation

Floor and ceil in BST relate to rounding numbers up or down on the number line, a concept in mathematics.

Recognizing floor and ceil as rounding operations connects discrete data structures to continuous math concepts.

Common Pitfalls

#1 Returning the node value immediately without checking if a better candidate exists.

Wrong approach:

function floorBST(root, target) {
if (!root) return null;
if (root.val <= target) return root.val;
return floorBST(root.left, target);
}

Correct approach:

function floorBST(root, target) {
if (!root) return null;
if (root.val === target) return root.val;
if (root.val > target) return floorBST(root.left, target);
const floorRight = floorBST(root.right, target);
return floorRight !== null ? floorRight : root.val;
}

Root cause:

Not exploring right subtree when current node is less than target misses closer floor candidates.

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

Wrong approach:

function ceilBST(root, target) {
if (!root) return null;
if (root.val === target) return root.val;
if (root.val > target) return ceilBST(root.right, target);
const ceilLeft = ceilBST(root.left, target);
return ceilLeft !== null ? ceilLeft : root.val;
}

Correct approach:

function ceilBST(root, target) {
if (!root) return null;
if (root.val === target) return root.val;
if (root.val < target) return ceilBST(root.right, target);
const ceilLeft = ceilBST(root.left, target);
return ceilLeft !== null ? ceilLeft : root.val;
}

Root cause:

Mixing up BST property directions causes wrong subtree exploration.

#3 Not handling null returns leading to runtime errors.

Wrong approach:

let floor = floorBST(root, target);
console.log(floor.toString()); // crashes if floor is null

Correct approach:

let floor = floorBST(root, target);
console.log(floor !== null ? floor.toString() : 'No floor found');

Root cause:

Assuming floor or ceil always exists ignores edge cases where no valid value is found.

Key Takeaways

Floor and ceil in BST find closest smaller-or-equal and larger-or-equal values efficiently by using the tree's sorted structure.

These operations rely on moving left or right based on comparisons and remembering the best candidate found so far.

Handling edge cases where floor or ceil does not exist is essential for robust code.

Iterative implementations can improve performance and avoid recursion limits in large trees.

Understanding floor and ceil deepens your grasp of BSTs and prepares you for advanced data structure queries.