Treap Path Probability

Problem

Return the probability that a treap built by inserting n keys in sorted order with random distinct priorities is a single path.

Sorted insertion always produces a right spine, and the heap property then forces priorities to increase with insertion order, which happens with probability 1 / n!. Return 0.0 for n <= 0.

Hint

Only one of the n! priority orderings keeps a sorted-insertion treap on a single spine.

Test cases

case 1

in: [1]

expected: 1

case 2

in: [3]

expected: 0.16666666666666666

case 3

in: [5]

expected: 0.008333333333333333

case 4

in: [0]

expected: 0

case 5

in: [10]

expected: 2.755731922398589e-7

Starter codePython

def treap_path_probability(n):
    # Your code here
    pass

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