Floor and Ceil in BST in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the floor of a value in a Binary Search Tree (BST)?

The floor of a value in a BST is the greatest value in the BST that is less than or equal to the given value.

beginner

What is the ceil of a value in a Binary Search Tree (BST)?

The ceil of a value in a BST is the smallest value in the BST that is greater than or equal to the given value.

intermediate

How does the BST property help in finding floor and ceil efficiently?

Because in a BST, left child nodes are smaller and right child nodes are larger, we can decide to move left or right at each step to find floor or ceil without checking all nodes.

beginner

In the BST floor search, if the current node's value is greater than the target, which subtree do we explore next?

We explore the left subtree because all values in the right subtree will be even greater, so they can't be floor if current node is already greater than target.

beginner

In the BST ceil search, if the current node's value is less than the target, which subtree do we explore next?

We explore the right subtree because all values in the left subtree are smaller, so they can't be ceil if current node is already less than target.

What does the floor of a value in a BST represent?

A The largest value less than or equal to the target

B The smallest value greater than or equal to the target

C The root value of the BST

D The smallest value in the BST

Floor is the greatest value in the BST that is less than or equal to the target value.

If the current node's value is equal to the target, what is the floor and ceil?

A Floor and ceil do not exist

B Floor is left child, ceil is right child

C Floor is right child, ceil is left child

D Floor and ceil are both the current node's value

If the node's value equals the target, both floor and ceil are that value.

When searching for ceil in BST, if current node's value is less than target, where do we go next?

A Left subtree

B Right subtree

C Stop search

D Return current node

We move to the right subtree to find a value greater than or equal to the target.

Which of these is true about floor and ceil in BST?

A Floor and ceil are always equal

B Floor is always greater than ceil

C Floor is always less than ceil or equal

D Floor and ceil do not depend on BST structure

Floor is the greatest value less than or equal to target, ceil is the smallest value greater than or equal to target, so floor ≤ ceil.

If no value in BST is less than or equal to target, what is the floor?

A Null or no floor exists

B Root value

C Smallest value in BST

D Largest value in BST

If no value ≤ target exists, floor does not exist (null).

Explain how to find the floor of a given value in a BST step-by-step.

Think about how BST ordering helps decide which subtree to explore.

Describe the difference between floor and ceil in a BST with examples.

Use simple numbers to illustrate the difference.