Floor and Ceil in BST in DSA Python - Execution Trace

Concept Flow - Floor and Ceil in BST

Start at root node

↓

Compare target with current node value

↓

Go right

↓

Update floor

↓

Repeat until no child to go

↓

Return floor and ceil values

Start from the root, compare target with node value, move left or right updating floor or ceil accordingly until no further move is possible.

Execution Sample

DSA Python

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def floor_ceil(root, target):
    floor = None
    ceil = None
    current = root
    while current:
        if current.val == target:
            floor = ceil = current.val
            break
        elif 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 from root and updating floor and ceil based on comparisons.

Execution Table

Step	Operation	Current Node Value	Target	Floor	Ceil	Pointer Move	Visual State
1	Start at root	8	6	None	None	At root	8 / \ 3 10 / \ 1 6 14 / \ 4 7 13
2	Compare 8 with 6	8	6	None	8	Go left	8 / \ 3 10 / \ 1 6 14 / \ 4 7 13
3	At node 3	3	6	3	8	Go right	8 / \ 3 10 / \ 1 6 14 / \ 4 7 13
4	At node 6	6	6	6	6	Found exact match, stop	8 / \ 3 10 / \ 1 6 14 / \ 4 7 13
5	Return	-	6	6	6	Done	Final floor=6, ceil=6

💡 Stopped at node with value equal to target (6), floor and ceil both set to 6.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
current.val	8	3	6	6	6
floor	None	None	3	6	6
ceil	None	8	8	6	6

Key Moments - 3 Insights

Why do we update floor only 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 is a candidate for floor. See execution_table step 3 where floor updates to 3.

Why do we update ceil only 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 is a candidate for ceil. See execution_table step 2 where ceil updates to 8.

What happens when we find a node with value exactly equal to target?

We set both floor and ceil to that value and stop searching because exact match means floor and ceil are the same. See execution_table step 4.

Visual Quiz - 3 Questions

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

A 3

B None

C 6

D 8

💡 Hint

Check the 'floor' column at step 3 in execution_table.

At which step does the pointer move to the left child?

A Step 3

B Step 4

C Step 2

D Step 1

💡 Hint

Look at the 'Pointer Move' column in execution_table for step 2.

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

A 3

B 8

C 6

D None

💡 Hint

Consider how ceil updates when current.val > target, see step 2 and 3 in execution_table.

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 exact match or no child
- Return floor and ceil values

Full Transcript

This visualization shows how to find floor and ceil values for a target in a Binary Search Tree (BST). Starting at the root, we compare the target with the current node's value. If the current node's value equals the target, both floor and ceil are set to this value and the search stops. If the current node's value is less than the target, we update floor to this value and move to the right child to find a closer floor. If the current node's value is greater than the target, we update ceil to this value and move to the left child to find a closer ceil. This process continues until we find an exact match or reach a leaf node. The execution table traces these steps with the current node, floor, ceil, and pointer moves. The variable tracker shows how floor and ceil update over time. Key moments clarify why floor updates only on less than target and ceil updates only on greater than target. The quiz tests understanding of these updates and pointer moves.

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 ceil is the smallest value greater than or equal to the given value, so The smallest value in the BST greater than or equal to the given value is incorrect. Options C and D do not relate 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 Python function signature to find the ceil of a value in a BST node?

easy

A. def ceil_find(value, root):

B. def find_ceil(root, value):

C. def findCeil(value):

D. def ceil(root):

Solution

1. Step 1: Check common parameter order for BST functions

   Functions usually take the root node first, then the value to search for.

2. Step 2: Validate each option

   def find_ceil(root, value): matches this order and naming convention. Options B, C, and D either have wrong parameter order or missing parameters.

3. Final Answer:

   def find_ceil(root, value): -> Option B

4. Quick Check:

   Function(root, value) is standard [OK]

Hint: Root node first, then value in function parameters [OK]

Common Mistakes:

• Swapping parameter order
• Missing one parameter
• Using unclear function names

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

       15
      /  \
     10   20
    /  \    \
   8   12    25

medium

A. 14

B. 15

C. 12

D. 10

Solution

1. Step 1: Locate values less than or equal to 14 in BST

   Values ≤ 14 are 10, 8, 12. 15 and above are greater.

2. Step 2: Find the greatest among these

   The greatest value ≤ 14 is 12.

3. Final Answer:

   12 -> Option C

4. Quick Check:

   Floor(14) = 12 [OK]

Hint: Floor ≤ value, pick largest from left subtree [OK]

Common Mistakes:

• Choosing 15 which is greater than 14
• Assuming floor equals the value if not present
• Picking smallest value instead of largest ≤ value

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

def find_ceil(root, value):
    if root is None:
        return None
    if root.val == value:
        return root.val
    if root.val < value:
        return find_ceil(root.right, value)
    else:
        ceil = find_ceil(root.left, value)
        return ceil if ceil is not None else root.val

What is the main error?

medium

A. It should check for None before recursion

B. It should return root.val when root.val == value

C. It should recurse on root.right when root.val > value

D. It should recurse on root.right when root.val < value

Solution

1. Step 1: Analyze recursion direction for ceil

   If root.val < value, ceil must be in right subtree, so recurse on root.right.

2. Step 2: Identify incorrect recursion

   Code incorrectly recurses on root.left when root.val < value, which is wrong.

3. Final Answer:

   It should recurse on root.right when root.val < value -> Option D

4. Quick Check:

   Ceil search goes right if root.val < value [OK]

Hint: Go right if node value < target for ceil [OK]

Common Mistakes:

• Recursing left instead of right
• Confusing floor and ceil logic
• Not handling None cases properly

5. You have a BST with values [5, 10, 15, 20, 25]. You want to find the floor and ceil of 17. Which pair is correct?

hard

A. Floor = 15, Ceil = 20

B. Floor = 20, Ceil = 25

C. Floor = 10, Ceil = 15

D. Floor = 17, Ceil = 17

Solution

1. Step 1: Identify floor of 17 in BST

   Floor is greatest value ≤ 17. Values ≤ 17 are 5, 10, 15. Greatest is 15.

2. Step 2: Identify ceil of 17 in BST

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

3. Final Answer:

   Floor = 15, Ceil = 20 -> Option A

4. Quick Check:

   Floor ≤ 17 = 15, Ceil ≥ 17 = 20 [OK]

Hint: Floor ≤ value, ceil ≥ value in sorted BST [OK]

Common Mistakes:

• Choosing floor or ceil outside BST values
• Assuming floor or ceil equals the value if not present
• Mixing floor and ceil values