Floor and Ceil in BST in DSA Typescript - 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 than scanning the whole tree.

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 current node's value, which subtree should you explore to find the floor?

You should explore the left subtree because all values in the right subtree are greater than the current node's value, which is already bigger than the target.

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

A The smallest value greater than or equal to the target

B The exact value only if it exists

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 is greater than the current node's value, where should you look to find the ceil?

A Right subtree

B Left subtree

C Current node only

D Both subtrees

Since the target is greater, the ceil must be in the right subtree or the current node if it matches.

When the current node's value equals the target, what is the floor and ceil?

A Floor is smaller, ceil is larger

B Both floor and ceil are the current node's value

C Floor is null, ceil is current node's value

D Floor is current node's value, ceil is null

Exact match means floor and ceil are the same as the current node's value.

Which property of BST helps in finding floor and ceil efficiently?

A Nodes are stored in a linked list

B Nodes are stored in a queue

C Left child is always smaller, right child is always larger

D All nodes have two children

BST property that left child < node < right child allows efficient search.

If the target value is smaller than the current node's value, which subtree is explored to find the ceil?

A Left subtree

B Right subtree

C Current node only

D No subtree

Since target is smaller, ceil could be the current node or in the left subtree.

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

Think about how BST ordering guides your search direction.

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

Use simple numbers to illustrate the concept.