Next Lower and Next Higher Ticket Number

A ticket office keeps issued ticket numbers in a binary search tree with distinct values. Given a number val that is in the tree, return [pred, succ]: the largest stored number strictly smaller than val and the smallest stored number strictly larger than val. Use None when there is no such number.

Examples

        50
       /  \
     30    70
    /  \     \
  20   40    80
    \
     25

Input:  root = build_tree([50, 30, 70, 20, 40, None, 80, None, 25]), val = 40
Output: [30, 50]

Input:  root = build_tree([50, 30, 70, 20, 40, None, 80, None, 25]), val = 20
Output: [None, 25]

Constraints

• 1 <= number of nodes <= 3000
• All values are distinct integers and val is present
• O(h) time, without listing all values

Goals

• Find the inorder predecessor and successor of a stored value in O(h)
• Handle values at the ends of the order