Floor and Ceil in BST in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Floor and Ceil for a given key in BST

What is the output of the floor and ceil values for key 15 in the given BST?

DSA Go

package main

import "fmt"

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

func floor(root *Node, key int) int {
    res := -1
    for root != nil {
        if root.val == key {
            return root.val
        } else if root.val > key {
            root = root.left
        } else {
            res = root.val
            root = root.right
        }
    }
    return res
}

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

func main() {
    root := &Node{20, nil, nil}
    root.left = &Node{10, nil, nil}
    root.right = &Node{30, nil, nil}
    root.left.left = &Node{5, nil, nil}
    root.left.right = &Node{15, nil, nil}
    root.right.left = &Node{25, nil, nil}
    root.right.right = &Node{35, nil, nil}

    f := floor(root, 15)
    c := ceil(root, 15)
    fmt.Printf("Floor: %d, Ceil: %d\n", f, c)
}

A Floor: 15, Ceil: 20

B Floor: 10, Ceil: 20

C Floor: 5, Ceil: 15

D Floor: 15, Ceil: 15

💡 Hint

Recall that floor is the greatest value less than or equal to the key, and ceil is the smallest value greater than or equal to the key.

Since 15 exists in the BST, both floor and ceil for 15 are 15 itself.

❓ Predict Output

intermediate

Floor and Ceil for a key not present in BST

What is the output of floor and ceil for key 17 in the BST?

DSA Go

package main

import "fmt"

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

func floor(root *Node, key int) int {
    res := -1
    for root != nil {
        if root.val == key {
            return root.val
        } else if root.val > key {
            root = root.left
        } else {
            res = root.val
            root = root.right
        }
    }
    return res
}

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

func main() {
    root := &Node{20, nil, nil}
    root.left = &Node{10, nil, nil}
    root.right = &Node{30, nil, nil}
    root.left.left = &Node{5, nil, nil}
    root.left.right = &Node{15, nil, nil}
    root.right.left = &Node{25, nil, nil}
    root.right.right = &Node{35, nil, nil}

    f := floor(root, 17)
    c := ceil(root, 17)
    fmt.Printf("Floor: %d, Ceil: %d\n", f, c)
}

A Floor: 10, Ceil: 25

B Floor: 15, Ceil: 20

C Floor: 17, Ceil: 17

D Floor: 20, Ceil: 25

💡 Hint

Floor is the greatest value less than or equal to 17, ceil is the smallest value greater than or equal to 17.

17 is not in the BST. The greatest value less than 17 is 15, and the smallest value greater than 17 is 20.

🔧 Debug

advanced

Identify the error in floor function implementation

What error will occur when running the floor function below for key 12?

DSA Go

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

A Nil pointer dereference runtime error

B Infinite loop

C Returns incorrect floor value

D Compilation error

💡 Hint

Check the conditions for moving left or right in the BST for floor calculation.

The conditions for moving left or right are swapped. It causes the function to return incorrect floor values.

❓ Predict Output

advanced

Floor and Ceil when key is smaller than all nodes

What is the output of floor and ceil for key 1 in the BST?

DSA Go

package main

import "fmt"

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

func floor(root *Node, key int) int {
    res := -1
    for root != nil {
        if root.val == key {
            return root.val
        } else if root.val > key {
            root = root.left
        } else {
            res = root.val
            root = root.right
        }
    }
    return res
}

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

func main() {
    root := &Node{20, nil, nil}
    root.left = &Node{10, nil, nil}
    root.right = &Node{30, nil, nil}
    root.left.left = &Node{5, nil, nil}
    root.left.right = &Node{15, nil, nil}
    root.right.left = &Node{25, nil, nil}
    root.right.right = &Node{35, nil, nil}

    f := floor(root, 1)
    c := ceil(root, 1)
    fmt.Printf("Floor: %d, Ceil: %d\n", f, c)
}

A Floor: -1, Ceil: 5

B Floor: 5, Ceil: 10

C Floor: -1, Ceil: -1

D Floor: 1, Ceil: 5

💡 Hint

If key is smaller than all nodes, floor should be -1 indicating no floor.

Since 1 is smaller than all nodes, floor returns -1 (no floor), ceil returns smallest node 5.

🧠 Conceptual

expert

Understanding floor and ceil behavior in BST with duplicates

In a BST that allows duplicate values inserted to the right subtree, what will be the floor and ceil of key 20 if the BST contains nodes with values [20, 20, 25, 15]?

A Floor: 20, Ceil: 20

B Floor: 15, Ceil: 25

C Floor: 20, Ceil: 25

D Floor: 15, Ceil: 20

💡 Hint

Even with duplicates inserted to the right subtree, since 20 exists, both floor and ceil are 20.

Since 20 exists in the BST (multiple times), both floor (greatest <= 20) and ceil (smallest >= 20) are 20.