Problem statement

https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/

Solution

First of all notice, that we will have ranges [1, 2), [2, 4), [4, 8), [8, 16) and so on in our layers. Let us look at say number 13, what its parent? First of all we need to find symmetric element in this row, which is 10 and then just use x -> x//2. How to find symmetric element? Sum of two symmetric elements is 3*2^x - 1, where x is the smallest value in this row.

Complexity

It is O(log n) for time and space.

Code

class Solution:
    def pathInZigZagTree(self, label):
        x = label.bit_length() - 1
        ans = [label]
        for i in range(x, 0, -1):
            label = (1<<i) * 3 - 1 - label
            label //= 2
            ans += [label]
        return ans[::-1]