Floor and Ceil in BST in DSA C++ - 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 BST nodes are ordered, we can decide to go left or right at each node to find floor or ceil without checking all nodes, making the search faster.

beginner

In a BST, if the current node's value is equal to the target value, what are the floor and ceil?

Both floor and ceil are the current node's value because it exactly matches the target.

intermediate

If the target value is smaller than the smallest value in the BST, what is the floor and ceil?

Floor does not exist (no value less than or equal), ceil is the smallest value in the BST.

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

A The average of all values in the BST

B The smallest value greater than or equal to the target

C The root value of the BST

D The greatest value less than or equal to the target

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

If the target value equals a node's value in BST, what is the ceil?

A The node's value itself

B A value smaller than the target

C The largest value in the BST

D No ceil exists

When the target equals a node's value, the ceil is that node's value.

Which direction do you move in BST if current node's value is greater than target when finding floor?

A Left subtree

B Stay at current node

C Right subtree

D No movement needed

If current node's value is greater than target, floor must be in left subtree or not exist.

What is the time complexity to find floor or ceil in a balanced BST?

A O(n log n)

B O(n)

C O(log n)

D O(1)

In a balanced BST, searching floor or ceil takes O(log n) time due to tree height.

If target is smaller than all BST values, what is the floor?

A Smallest BST value

B No floor exists

C Target itself

D Largest BST value

No floor exists if target is smaller than all values in BST.

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

Think about how BST ordering helps decide direction.

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

Use a simple BST and a target value between nodes.