BST Floor and Ceil

Problem

Find the floor and ceiling of a target in a binary search tree.

Insert values in order (duplicates ignored), then walk from the root: when the node value is less than the target record it as the floor and go right; when it is greater record it as the ceiling and go left; stop at an exact match.

Return [floor, ceiling] with None for missing entries.

Hint

Smaller nodes are floor candidates on the way right; larger nodes are ceiling candidates on the way left.

Test cases

case 1

in: [[8,4,12,2,6,10,14],5]

expected: [4,6]

case 2

in: [[8,4,12],8]

expected: [8,8]

case 3

in: [[8,4,12],3]

expected: [null,4]

case 4

in: [[],5]

expected: [null,null]

case 5

in: [[5,3,7],6]

expected: [5,7]

Starter codePython

def bst_floor_ceil(values, target):
    # Your code here
    pass

5 test cases · run your code against them in the editor