Floor and Ceil in BST in DSA Go - Build from Scratch

Floor and Ceil in BST

📖 Scenario: You are working with a Binary Search Tree (BST) that stores integer values. You want to find the floor and ceil values for a given number in the BST. The floor is the greatest value in the BST less than or equal to the given number. The ceil is the smallest value in the BST greater than or equal to the given number.This is useful in many real-world cases like finding closest available prices, dates, or scores.

🎯 Goal: Build a Go program that creates a BST, sets a target number, finds the floor and ceil values for that number in the BST, and prints the results.

📋 What You'll Learn

Create a BST with exact nodes: 20, 10, 30, 5, 15, 25, 35

Set a target number variable called target with value 16

Implement functions floorBST and ceilBST to find floor and ceil values

Print the floor and ceil values for the target number

💡 Why This Matters

🌍 Real World

Finding floor and ceil values in a BST is useful in applications like price matching, scheduling, and range queries where you want closest available values.

💼 Career

Understanding BST operations and floor/ceil logic is important for software engineers working on search engines, databases, and real-time systems.

1

Create the BST structure and insert nodes

Create a struct called Node with data int, left *Node, and right *Node. Then create a function insert that takes a *Node and an int and returns a *Node. Insert these exact values into the BST in this order: 20, 10, 30, 5, 15, 25, 35. Store the root in a variable called root.

DSA Go

// Define Node struct and insert function
// Insert nodes 20, 10, 30, 5, 15, 25, 35 into BST
// Store root in variable root

Hint

Define the Node struct with data, left, and right pointers. Use recursion in insert to place values correctly.

2

Set the target number to find floor and ceil

Create an integer variable called target and set it to 16.

DSA Go

package main

import "fmt"

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

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

func main() {
    var root *Node
    root = insert(root, 20)
    root = insert(root, 10)
    root = insert(root, 30)
    root = insert(root, 5)
    root = insert(root, 15)
    root = insert(root, 25)
    root = insert(root, 35)

    // Create target variable
    // Your code here
}

Hint

Use target := 16 to create and set the variable.

3

Implement floorBST and ceilBST functions

Write two functions: floorBST and ceilBST. Each takes root *Node and target int and returns an int. floorBST returns the greatest value less than or equal to target in the BST or -1 if none. ceilBST returns the smallest value greater than or equal to target or -1 if none.

DSA Go

package main

import "fmt"

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

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

// Write floorBST function here
// Write ceilBST function here

func main() {
    var root *Node
    root = insert(root, 20)
    root = insert(root, 10)
    root = insert(root, 30)
    root = insert(root, 5)
    root = insert(root, 15)
    root = insert(root, 25)
    root = insert(root, 35)

    target := 16

    // Your code here
}

Hint

Use a loop to traverse the BST. Update floor when current node is less than target. Update ceil when current node is greater than target.

4

Print the floor and ceil values for the target

Print the floor value using floorBST(root, target) and the ceil value using ceilBST(root, target) with the exact format:
Floor: X
Ceil: Y
where X and Y are the floor and ceil values respectively.

DSA Go

package main

import "fmt"

// Previous code

func main() {
    var root *Node
    root = insert(root, 20)
    root = insert(root, 10)
    root = insert(root, 30)
    root = insert(root, 5)
    root = insert(root, 15)
    root = insert(root, 25)
    root = insert(root, 35)

    target := 16

    // Print floor and ceil values
    // Your code here
}

Hint

Use fmt.Printf("Floor: %d\n", floorBST(root, target)) and similarly for ceil.