Floor and Ceil in BST in DSA Go

Mental Model

Floor is the biggest value smaller or equal to target; Ceil is the smallest value bigger or equal to target in the BST.

Analogy: Imagine a bookshelf sorted by book height. Floor is the tallest book not taller than your target height, and Ceil is the shortest book not shorter than your target height.

       8
      / \
     4   12
    / \   / \
   2   6 10  14

Dry Run Walkthrough

Input: BST: 8->4->12->2->6->10->14, find floor and ceil of 5

Goal: Find the floor and ceil values for 5 in the BST

Step 1: Start at root node 8, compare 5 with 8

8[compare with 5] -> 4 -> 12 -> 2 -> 6 -> 10 -> 14

Why: We start at root to decide which subtree to explore

Step 2: Since 5 < 8, move to left child 4

8 -> 4[compare with 5] -> 12 -> 2 -> 6 -> 10 -> 14

Why: Values smaller than 8 are in left subtree

Step 3: Since 5 > 4, floor candidate updated to 4, move to right child 6

8 -> 4[floor=4] -> 12 -> 2 -> 6[compare with 5] -> 10 -> 14

Why: 4 is less than 5, so it could be floor; check right subtree for closer value

Step 4: Since 5 < 6, ceil candidate updated to 6, move to left child which is null

8 -> 4[floor=4] -> 12 -> 2 -> 6[ceil=6] -> 10 -> 14

Why: 6 is greater than 5, so it could be ceil; no left child to explore

Step 5: No more nodes to explore, return floor=4 and ceil=6

Final floor=4, ceil=6

Why: We found closest smaller and bigger values around 5

Result:

4 -> 6

Annotated Code

DSA Go

package main

import "fmt"

type Node struct {
	val   int
	left  *Node
	right *Node
}

func insert(root *Node, val int) *Node {
	if root == nil {
		return &Node{val: val}
	}
	if val < root.val {
		root.left = insert(root.left, val)
	} else {
		root.right = insert(root.right, val)
	}
	return root
}

func floorCeil(root *Node, target int) (floor *int, ceil *int) {
	var f, c *int
	curr := root
	for curr != nil {
		if curr.val == target {
			f = &curr.val
			c = &curr.val
			break
		} else if curr.val > target {
			c = &curr.val // update ceil candidate
			curr = curr.left // go left to find smaller or equal
		} else {
			f = &curr.val // update floor candidate
			curr = curr.right // go right to find bigger or equal
		}
	}
	return f, c
}

func main() {
	var root *Node
	values := []int{8, 4, 12, 2, 6, 10, 14}
	for _, v := range values {
		root = insert(root, v)
	}
	floor, ceil := floorCeil(root, 5)
	if floor != nil {
		fmt.Printf("Floor: %d\n", *floor)
	} else {
		fmt.Println("Floor: nil")
	}
	if ceil != nil {
		fmt.Printf("Ceil: %d\n", *ceil)
	} else {
		fmt.Println("Ceil: nil")
	}
}

for curr != nil {

loop through nodes to find floor and ceil candidates

if curr.val == target {

exact match found, floor and ceil are the same

else if curr.val > target {

current node value is bigger, update ceil and go left

else {

current node value is smaller, update floor and go right

Output

Floor: 4

Ceil: 6

Complexity Analysis

Time: O(h) where h is the height of the BST because we traverse from root down to a leaf at most once

Space: O(1) because we use only a few pointers and no extra data structures

vs Alternative: Compared to scanning all nodes (O(n)), this approach uses BST properties to find floor and ceil efficiently in O(h)

Edge Cases

target smaller than all nodes

floor is nil, ceil is smallest node

DSA Go

c = &curr.val // update ceil candidate

target larger than all nodes

ceil is nil, floor is largest node

DSA Go

f = &curr.val // update floor candidate

target equals a node value

floor and ceil both equal target

DSA Go

if curr.val == target { f = &curr.val; c = &curr.val; break }

When to Use This Pattern

When asked to find closest smaller or bigger values in a BST, use floor and ceil search by moving left or right based on comparisons.

Common Mistakes

Mistake: Not updating floor or ceil candidates correctly when moving left or right
Fix: Update floor when moving right (smaller values), update ceil when moving left (bigger values)

Summary

Find the closest smaller or equal (floor) and closest bigger or equal (ceil) values to a target in a BST.

Use when you need nearest bounds of a value in a sorted tree structure.

The key is to move left or right while updating floor or ceil candidates based on comparisons.