A ticket kiosk files each new ticket number into a binary search tree in the order the tickets are
issued, order (distinct integers): starting at the root, it compares the new number with the
node there and moves left if smaller, right if larger, until it finds an empty spot. Every node it
compares with counts as one comparison; the very first ticket becomes the root with 0
comparisons.
Return a list with the number of comparisons made for each ticket, in issue order.
Examples
Input: order = [50, 30, 70, 40, 35, 80]
Output: [0, 1, 1, 2, 3, 2]
Explanation: 35 is compared with 50, 30 and 40 before landing left of 40.
Input: order = [1, 2, 3]
Output: [0, 1, 2]
Constraints
0 <= len(order) <= 10**5, values are distinct,-10**9 <= order[i] <= 10**9- The tree can grow as tall as the input, so simulating the kiosk is far too slow.
Goals
- Prove that a new key's parent is its nearest smaller or nearest larger earlier key
- Find those neighbours for every key by deleting from a sorted linked list in reverse
- Avoid walking down a tree that can be as tall as the input