Iterative Segment Tree Ancestor Path

Problem

List the ancestors of a leaf in an iterative segment tree.

A 2n iterative segment tree stores leaf i at index n + i and each parent at index // 2, with the root at index 1. Return the path of indices starting at the leaf and ending at the root.

Return the list of ancestor indices.

Hint

Every parent index is the integer division of its child by two.

Test cases

case 1

in: [4,0]

expected: [4,2,1]

case 2

in: [4,3]

expected: [7,3,1]

case 3

in: [1,0]

expected: [1]

case 4

in: [8,5]

expected: [13,6,3,1]

case 5

in: [8,7]

expected: [15,7,3,1]

Starter codePython

def segtree_ancestor_path(n, i):
    # Your code here
    pass

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