Floor and Ceil in BST in DSA Go - Execution Trace

Concept Flow - Floor and Ceil in BST

Start at root

↓

Compare key with node value

↓

Floor = Ceil = node value

→Done

↓

Go to left subtree

↓

Go to right subtree

↓

Repeat until leaf

↓

Return floor and ceil found

Start from the root and compare the key with current node's value. Move left if key is smaller, right if larger, updating floor or ceil candidates until reaching a leaf.

Execution Sample

DSA Go

func floorCeil(root *Node, key int) (floor, ceil int) {
    floor, ceil = -1, -1
    current := root
    for current != nil {
        if current.val == key {
            floor, ceil = current.val, current.val
            break
        } else if key < current.val {
            ceil = current.val
            current = current.left
        } else {
            floor = current.val
            current = current.right
        }
    }
    return
}

Find floor and ceil of a key in BST by traversing from root, updating floor and ceil candidates based on comparisons.

Execution Table

Step	Operation	Current Node Value	Key	Floor	Ceil	Pointer Move	Visual State
1	Start at root	20	18	-1	-1	Compare 18 < 20, move left	20 / \ 10 30 / \ 5 15 40
2	Move to left child	10	18	-1	20	Compare 18 > 10, floor=10, move right	20 / \ 10 30 / \ 5 15 40
3	Move to right child	15	18	10	20	Compare 18 > 15, floor=15, move right	20 / \ 10 30 / \ 5 15 40
4	Move to right child	nil	18	15	20	Reached leaf, stop	20 / \ 10 30 / \ 5 15 40
Exit	Return floor and ceil	nil	18	15	20	Done	Floor=15, Ceil=20

💡 Reached leaf node (nil), no more nodes to check, return floor=15 and ceil=20

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
current.val	20	20	10	15	nil	nil
floor	-1	-1	10	15	15	15
ceil	-1	20	20	20	20	20

Key Moments - 3 Insights

Why do we update floor only when key > current node value?

Because floor is the greatest value less than or equal to key. When key > current node, current node is a candidate floor. See execution_table rows 2 and 3 where floor updates to 10 and then 15.

Why do we update ceil only when key < current node value?

Because ceil is the smallest value greater than or equal to key. When key < current node, current node is a candidate ceil. See execution_table row 1 where ceil updates to 20.

What happens if key equals a node value?

Both floor and ceil are that node's value, and we stop searching immediately. This is shown in the code with the equality check and break.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the value of floor?

A 10

B 15

C 20

D -1

💡 Hint

Check the 'Floor' column at Step 3 in execution_table

At which step does the pointer move to a nil node?

A Step 2

B Step 3

C Step 4

D Exit

💡 Hint

Look at the 'Pointer Move' and 'Current Node Value' columns in execution_table

If the key was 30, what would be the floor and ceil after the first step?

A Floor = 20, Ceil = -1

B Floor = -1, Ceil = 20

C Floor = 20, Ceil = 30

D Floor = 30, Ceil = 30

💡 Hint

When key > current node value, floor updates; see variable_tracker and concept_flow

Concept Snapshot

Floor and Ceil in BST:
- Floor: greatest value ≤ key
- Ceil: smallest value ≥ key
- Start at root, compare key with node
- Move left if key < node (update ceil)
- Move right if key > node (update floor)
- Stop if key == node
- Return last floor and ceil found

Full Transcript

To find floor and ceil in a BST, start at the root node. Compare the key with the current node's value. If they are equal, floor and ceil are both that value. If the key is less than the node's value, update ceil to the node's value and move to the left child. If the key is greater, update floor to the node's value and move to the right child. Repeat this until you reach a leaf node. The last updated floor and ceil values are the answers. This process efficiently uses BST properties to find floor and ceil without checking all nodes.