BST Successor and Predecessor

Problem

Find the successor and predecessor of a key in a binary search tree.

Insert values in order (duplicates ignored). The successor is the smallest value strictly greater than key and the predecessor is the largest value strictly smaller. Walk from the root keeping candidates, and when the key is found take the minimum of its right subtree and the maximum of its left subtree.

Return [successor, predecessor] with None for missing entries.

Hint

Ancestors passed while descending left are successor candidates; those passed descending right are predecessor candidates.

Test cases

case 1

in: [[20,8,22,4,12,10,14],8]

expected: [10,4]

case 2

in: [[20,8,22,4,12,10,14],14]

expected: [20,12]

case 3

in: [[20,8,22,4,12,10,14],25]

expected: [null,22]

case 4

in: [[5],5]

expected: [null,null]

case 5

in: [[],3]

expected: [null,null]

Starter codePython

def bst_successor_predecessor(values, key):
    # Your code here
    pass

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