Finding the floor and the ceiling in a binary search tree

Question

I've been struggling with a code problem where I have to find the floor and the ceiling of a given number in a binary search tree. For example, 5 is given, so the program should print 4 for floor and 6 for ceiling if they exist. Otherwise, it should print None for each of them.

Here is a sample code to explain:

class Node:
   def __init__(self, value):
   self.left = None
   self.right = None
   self.value = value

def findCeilingFloor(root_node, k, floor=None, ceil=None):
    # Fill this in.

root = Node(8) 
root.left = Node(4) 
root.right = Node(12) 

root.left.left = Node(2) 
root.left.right = Node(6) 

root.right.left = Node(10) 
root.right.right = Node(14) 

print findCeilingFloor(root, 5)
# (4, 6)

I implemented some code for the findCeilingFloor function. Although it finds and assigns the floor and the ceiling values, when the program turns back to the node which contains 12 as the value, it changes the floor and the ceiling value to None again. Therefore, it always returns None for both of them. I added some print statements to keep track what's going on.

Here is my output:

Problem output

And here is my implementation:

def findCeilingFloor(root_node, k, floor=None, ceil=None):
    # Fill this in.
    print(f"Current node value = {root_node.value}")
    print(f"Floor value = {floor}")
    print(f"Ceil value = {ceil}")
    print()

    if root_node.value == k - 1:
        floor = root_node.value

    if root_node.value == k + 1:
        ceil = root_node.value

    if root_node.left:
        findCeilingFloor(root_node.left, k, floor, ceil)

    if root_node.right:
        findCeilingFloor(root_node.right, k, floor, ceil)

    return floor, ceil

I didn't understand why my code returns None for both of them even though it finds both the floor and the ceil values(the ceil value doesn't appear on the output because it prints right before it assigns the ceil, I checked that if it finds the ceil as well). When there is no node left to go at the left subtree, it directs to the right subtree, to 12, and then both the floor and the ceil becomes None.

Answer 1

There is one main issue with your code.

Passing parameters to a function does not work the way you think

Look at the following code and try to guess the output, then compare with the actual output:

def f(x):
  g(x)
  return x

def g(x):
  x = 3

print(f(4))

So, is the output 3, or 4? Try it yourself. As it turns out, function g does not modify f's variable x. The statement x = 3 in the body of g assigns a local variable called x which is not the same as f's.

Fixing the code

def findCeilingFloor(root_node, k):
    # Fill this in.
    print(f"Current node value = {root_node.value}")
    print(f"Floor value = {floor}")
    print(f"Ceil value = {ceil}")
    print()

    floor, ceil = None, None

    if root_node.value == k - 1:
        floor = root_node.value
    elif root_node.left:
        floor = findCeilingFloor(root_node.left, k, floor, ceil)

    if root_node.value == k + 1:
        ceil = root_node.value
    elif root_node.right:
        ceil = findCeilingFloor(root_node.right, k, floor, ceil)

    return floor, ceil

Another issue: meaning of floor and ceil

There is most likely another issue. It is possible that you have misunderstood what "floor" and "ceil" were supposed to be. Are you sure that those refer to the values k-1 and k+1 exactly? It is possible that what you are looking for is the largest value less than k in the tree, for floor, and the smallest value more than k in the tree, for ceil.