Floor and Ceil in BST in DSA Javascript - Execution Trace

Concept Flow - Floor and Ceil in BST

Start at root node

↓

Compare target with current node value

↓

Go left

↓

Update floor

↓

Repeat until leaf node

↓

Return floor and ceil values

Start from the root, compare target with node value, move left or right updating floor or ceil until no more nodes to visit.

Execution Sample

DSA Javascript

function floorCeilBST(root, target) {
  let floor = null, ceil = null;
  let current = root;
  while (current) {
    if (current.val === target) return { floor: target, ceil: target };
    else if (current.val < target) {
      floor = current.val;
      current = current.right;
    } else {
      ceil = current.val;
      current = current.left;
    }
  }
  return { floor, ceil };
}

Find floor and ceil of target in BST by traversing and updating floor or ceil accordingly.

Execution Table

Step	Operation	Current Node Value	Target	Floor	Ceil	Pointer Move	Visual State
1	Start at root	8	6	null	null	Compare 6 with 8	8 / \ 3 10 / \ 1 6 14
2	target=6 < current=8, update ceil=8	8	6	null	8	Move left	8 / \ 3 10 / \ 1 6 14
3	At node 3, 3 < 6	3	6	3	8	Move right	8 / \ 3 10 / \ 1 6 14
4	At node 6, 6 == 6	6	6	6	6	Found exact match	8 / \ 3 10 / \ 1 6 14
5	Return floor and ceil	-	6	6	6	Stop	8 / \ 3 10 / \ 1 6 14

💡 Exact match found at node with value 6, floor and ceil both are 6.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
floor	null	null	null	3	6	6
ceil	null	null	8	8	6	6
current	root(8)	8	3	6	6	null

Key Moments - 3 Insights

Why do we update floor when current node value is less than target?

Because floor is the greatest value less than or equal to target. When current.val < target, current.val can be a candidate floor. See execution_table step 3 where floor updates to 3.

Why do we update ceil when current node value is greater than target?

Because ceil is the smallest value greater than or equal to target. When current.val > target, current.val can be a candidate ceil. See execution_table step 2 where ceil updates to 8.

What happens if target matches a node value exactly?

We return that value as both floor and ceil immediately. See execution_table step 4 where current.val == target, so floor and ceil both become 6.

Visual Quiz - 3 Questions

Look at the execution_table, what is the floor value after step 3?

A null

B 6

C 3

D 8

💡 Hint

Check the 'Floor' column in execution_table row for step 3.

At which step does the algorithm find an exact match for the target?

A Step 4

B Step 3

C Step 2

D Step 5

💡 Hint

Look for the step where current node value equals target in execution_table.

If the target was 5 instead of 6, what would be the ceil after step 3?

A 3

B 8

C 6

D null

💡 Hint

Check the 'Ceil' column in execution_table and variable_tracker after step 3.

Concept Snapshot

Floor and Ceil in BST:
- Floor: greatest value ≤ target
- Ceil: smallest value ≥ target
- Start at root, compare target with node
- Move left if node ≥ target (update ceil)
- Move right if node < target (update floor)
- Stop when node is null or exact match found

Full Transcript

To find floor and ceil in a BST, start at the root node. Compare the target with the current node's value. If the current node's value equals the target, return it as both floor and ceil. If the current node's value is less than the target, update floor to current node's value and move right. If greater, update ceil and move left. Repeat until no more nodes to visit. The final floor and ceil are returned. This method efficiently uses BST properties to find closest values.

Practice

1. What does the floor of a value in a Binary Search Tree (BST) represent?

easy

A. The greatest value in the BST less than or equal to the given value

B. The smallest value in the BST greater than or equal to the given value

C. The root value of the BST

D. The average of all values in the BST

Solution

1. Step 1: Understand the floor concept in BST

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

2. Step 2: Compare with other options

   The smallest value in the BST greater than or equal to the given value describes the ceil, not the floor. Options C and D are unrelated to floor.

3. Final Answer:

   The greatest value in the BST less than or equal to the given value -> Option A

4. Quick Check:

   Floor = greatest ≤ value [OK]

Hint: Floor is largest value ≤ target in BST [OK]

Common Mistakes:

• Confusing floor with ceil
• Thinking floor is the smallest value
• Assuming floor is always the root

2. Which of the following is the correct JavaScript function signature to find the ceil of a value in a BST?

easy

A. function ceilFind(value, root) {}

B. function findFloor(value) {}

C. function findCeil(root, value) {}

D. function ceil(root) {}

Solution

1. Step 1: Identify correct parameter order and naming

   The function to find ceil should take the BST root and the target value as parameters, typically as (root, value).

2. Step 2: Check options for correct signature

   function findCeil(root, value) {} matches this pattern. function ceilFind(value, root) {} reverses parameters, C is for floor and missing root, D misses value parameter.

3. Final Answer:

   function findCeil(root, value) {} -> Option C

4. Quick Check:

   Correct params: root, value [OK]

Hint: Function needs root and value parameters [OK]

Common Mistakes:

• Swapping parameter order
• Missing root or value parameter
• Using wrong function name

3. Given the BST below and value = 14, what is the floor of 14?

       15
      /  \
     10  20
    /  \   \
   8   12  25

medium

A. 15

B. 10

C. 14

D. 12

Solution

1. Step 1: Locate floor value in BST for 14

   Floor is greatest value ≤ 14. Values ≤ 14 are 8, 10, 12. 12 is the greatest among these.

2. Step 2: Confirm no value closer to 14 exists

   15 is greater than 14, so not floor. 14 is not in BST.

3. Final Answer:

   12 -> Option D

4. Quick Check:

   Floor(14) = 12 [OK]

Hint: Floor ≤ value, pick largest such node [OK]

Common Mistakes:

• Choosing 15 which is > 14
• Assuming floor must be exact value
• Picking smaller values like 10 instead of 12

4. Consider this buggy JavaScript code to find ceil in BST:

function findCeil(root, value) {
  if (!root) return -1;
  if (root.val === value) return root.val;
  if (root.val < value) return findCeil(root.right, value);
  let ceil = findCeil(root.left, value);
  return (ceil >= value) ? ceil : root.val;
}

What is the main error?

medium

A. It searches left subtree when root.val < value instead of right

B. It returns -1 when root is null instead of null

C. It compares ceil with value incorrectly

D. It does not handle root.val === value case

Solution

1. Step 1: Analyze subtree traversal logic

   If root.val < value, ceil must be in right subtree, but code wrongly searches left subtree.

2. Step 2: Check other parts

   Return -1 is acceptable as sentinel. Comparison and equality check are correct.

3. Final Answer:

   It searches left subtree when root.val < value instead of right -> Option A

4. Quick Check:

   Wrong subtree chosen for root.val < value [OK]

Hint: Go right if root.val < value for ceil [OK]

Common Mistakes:

• Searching wrong subtree
• Ignoring base case
• Incorrect comparison logic

5. You want to find both floor and ceil of value 17 in this BST:

       16
      /  \
     10  20
    /  \   \
   8   12  25

Which pair is correct?

hard

A. [16, 17]

B. [16, 20]

C. [17, 20]

D. [15, 20]

Solution

1. Step 1: Find floor of 17

   Floor is greatest value ≤ 17. Values ≤ 17 are 8, 10, 12, 16. Largest is 16.

2. Step 2: Find ceil of 17

   Ceil is smallest value ≥ 17. Values ≥ 17 are 20, 25. Smallest is 20.

3. Final Answer:

   [16, 20] -> Option B

4. Quick Check:

   Floor=16, Ceil=20 [OK]

Hint: Floor ≤ value, ceil ≥ value, pick closest [OK]

Common Mistakes:

• Assuming floor or ceil equals value if not present
• Choosing wrong subtree values
• Mixing floor and ceil values