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.

Practice

1. What does the floor of a value in a Binary Search Tree (BST) represent?

easy

A. The smallest value in the BST less than 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 greatest value in the BST less than or equal to the given value

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 options

   The greatest value in the BST less than or equal to the given value matches this definition exactly, while others describe different concepts.

3. Final Answer:

   The greatest value in the BST less than or equal to the given value -> Option D

4. Quick Check:

   Floor = greatest ≤ value [OK]

Hint: Floor is largest ≤ value in BST [OK]

Common Mistakes:

• Confusing floor with ceil
• Thinking floor is smallest value
• Assuming floor is always root

2. Which of the following Go function signatures correctly represents a function to find the ceil in a BST for an integer key?

easy

A. func ceil(root *Node, key int) int

B. func ceil(key int, root *Node) int

C. func ceil(root Node, key int) int

D. func ceil(root *Node, key string) int

Solution

1. Step 1: Check parameter order and types

   The function should take a pointer to the root node and an integer key to search for ceil.

2. Step 2: Validate options

   func ceil(root *Node, key int) int uses pointer to Node and int key in correct order. Swapping parameters to key first is wrong, using value Node instead of pointer is wrong, using string for key is wrong.

3. Final Answer:

   func ceil(root *Node, key int) int -> Option A

4. Quick Check:

   Pointer root and int key correct [OK]

Hint: Pointer root first, key int second [OK]

Common Mistakes:

• Swapping parameter order
• Using value instead of pointer for root
• Wrong key data type

3. Given the BST below and key = 14, what is the ceil value returned by the following Go code?

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

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

// BST structure:
//       10
//      /  \
//     5    15
//         /  \
//        12   20

// Call: ceil(root, 14)

medium

A. 15

B. 12

C. 20

D. -1

Solution

1. Step 1: Trace ceil function with key=14

   Start at root 10: 10 < 14, go right to 15. 15 > 14, check left subtree of 15 (12). 12 < 14, so ceil(12) returns -1, so return 15.

2. Step 2: Confirm returned ceil value

   Ceil is 15, the smallest value ≥ 14 in BST.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Ceil(14) = 15 [OK]

Hint: Ceil is smallest ≥ key, check right if less [OK]

Common Mistakes:

• Returning 12 instead of 15
• Returning -1 when ceil exists
• Confusing floor and ceil logic

4. The following Go code attempts to find the floor in a BST but returns incorrect results. What is the bug?

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

medium

A. The function should check 'floorVal >= key' instead

B. The condition 'floorVal <= key' should be 'floorVal != -1'

C. The base case should return 0 instead of -1

D. The recursive call on left subtree is incorrect

Solution

1. Step 1: Analyze floorVal condition

   The code checks if floorVal <= key, but floorVal can be -1 (no floor found). This causes wrong returns.

2. Step 2: Correct condition for valid floorVal

   It should check if floorVal != -1 to confirm a valid floor before returning it; otherwise return root.val.

3. Final Answer:

   The condition 'floorVal <= key' should be 'floorVal != -1' -> Option B

4. Quick Check:

   Check floorVal != -1 before return [OK]

Hint: Check for -1 (no floor) before returning floorVal [OK]

Common Mistakes:

• Ignoring -1 as invalid floor
• Wrong comparison operators
• Changing base case return value

5. You have a BST with nodes: 8, 4, 12, 2, 6, 10, 14. You want to find both floor and ceil for key = 5 using a single traversal function. Which approach is best to implement this efficiently?

hard

A. Use inorder traversal and store all nodes in array, then binary search

B. Traverse left subtree for floor, right subtree for ceil separately

C. Traverse once, update floor when node.val ≤ key, update ceil when node.val ≥ key

D. Find floor first, then restart traversal to find ceil

Solution

1. Step 1: Understand single traversal for floor and ceil

   During one traversal, compare node values with key. Update floor if node.val ≤ key and is greater than current floor. Update ceil if node.val ≥ key and is less than current ceil.

2. Step 2: Compare approaches

   Traverse once, update floor when node.val ≤ key, update ceil when node.val ≥ key efficiently finds both in one pass. Options B and C require multiple traversals. Use inorder traversal and store all nodes in array, then binary search uses extra space and is less efficient.

3. Final Answer:

   Traverse once, update floor when node.val ≤ key, update ceil when node.val ≥ key -> Option C

4. Quick Check:

   Single pass update floor & ceil [OK]

Hint: Update floor and ceil in one BST traversal [OK]

Common Mistakes:

• Doing separate traversals for floor and ceil
• Using extra space unnecessarily
• Restarting traversal multiple times