In an infinite binary tree where every node has two children, the nodes are labelled in row order.
In the odd numbered rows (ie., the first, third, fifth,...), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,...), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.
 
Example 1:
Input: label = 14
Output: [1,3,4,14]

Example 2:
Input: label = 26
Output: [1,2,6,10,26]

 
Constraints:

1 <= label <= 10^6

Difficulty: interview

Starter code:

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        

Solutions:
class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        res = []
        level = 0
        nodes_count = 0
        while nodes_count < label:
            nodes_count += 2**level
            level += 1
        while label != 0:
            res.append(label)
            level_max = (2**level) - 1
            level_min = 2**(level-1)
            label = (level_max + level_min - label) // 2
            level -= 1
        return res[::-1]



import math
class Solution:
        
    def pathInZigZagTree(self, label: int) -> List[int]:
        res=[]
        level=math.ceil(math.log(label+1,2))
        res.append(label)
        if level%2==1:
            label=label//2
            level-=1
            label=abs(pow(2,level)-label)+pow(2,level-1)-1
            res.append(label)
        
        while(label>=1):
            if level%2==1:
                level-=1
                label=label//2
                res.append(label)
            else:
                label=label//2
                level-=1
                res.append(abs(pow(2,level)-label)+pow(2,level-1)-1)
        res.pop()
        
        return res[::-1]
        
        # return [pow(2,x) for x in range(math.ceil(math.log(label,2)))]
        # l=[]
        # for i in range(1,math.ceil(math.log(label,2))):
        #     if i%2==1:
        #         l.extend([ temp for temp in range(pow(2,i-1),pow(2,i)) ])
        #     else:
        #         l.extend([temp for temp in range(pow(2,i),pow(2,i-1),-1)])
        # return l


import math
class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        def findIndexorLabel(value):
            level = int(math.log(value, 2)) + 1
            if level%2:
                index = value
            else:
                total = 2**(level-1) + (2**level - 1)
                index = total - value
            return index
        arr = []
        arr.insert(0, label)
        index = findIndexorLabel(label)
        parentNode = index//2
        while parentNode != 0:
            nodeVal = findIndexorLabel(parentNode)
            arr.insert(0, nodeVal)
            index = findIndexorLabel(nodeVal)
            parentNode = index//2
        return arr
        
                


class Solution:
    def pathInZigZagTree(self, label: int):
        out = []
        while(label >= 1):
            out.append(label)
            label = self.swap(label)
        return out[::-1]
        
    def swap(self, x):
        to = 1
        while(to <= x):
            to = to << 1
        return (to + (to >> 1) -1 - x) // 2


class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        ans = [label]
        while label:
            llen = len(bin(label)[2:])
            label = ( pow(2, llen) -1 - label + pow(2, llen-1) ) // 2
            ans.append(label)
\t\t
        return ans[-2::-1]
        

import numpy as np

class Solution:
    def parent(self, label:int) -> int:
        # find out in which row you are.
        row = int(np.log2(label))
        # how many steps to first in that row
        counter = label - 2**row
        parent = label - (counter + int(counter / 2) + 1)
        return parent

    def pathInZigZagTree(self, label: int) -> List[int]:
        # make it recursive
        sol = []
        while True:
            sol.append(label)
            print(sol)
            if label > 1:
                label = Solution.parent(self, label)
            else:
                break
        return sol[::-1]

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        n=label
        change=False
        stack=[]
        index=-1
        while(n>0):
            stack.append(n)
            n=int(n/2)
            index+=1
        check=False
        output=[]
        while(stack):
            p=stack.pop(0)
            if not check:
                output.append(p)
            else:
                start=pow(2,index)
                end=pow(2,index+1)-1
                while(start<=end):
                    if p==start:
                        output.append(end)
                        break
                    elif p==end:
                        output.append(start)
                        break
                    start+=1
                    end-=1
            check=not check
            index-=1
        return output[::-1]


class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        # 1. Generate non-zig path
        path = [label]
        while label != 1:
            label = label // 2
            path.append(label)
        print(path)
        path.reverse()
        
        odd = len(path) % 2 != 0
        # 2. Account for zig-zag
        for i in range(1, len(path)-1):
            if not odd and i % 2 == 0:
                print(\"Here\")
                level = [i for i in range(2**(i+1)-1, 2**i-1,-1)]
                index = path[i] - 2**i
                path[i] = level[index]
            elif odd and i % 2 != 0:
                level = [i for i in range(2**(i+1)-1, 2**i-1,-1)]
                index = path[i] - 2**i
                path[i] = level[index]
        
        return path
            

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        ans = [label]
        i = math.floor(math.log(label,2))
        while i >= 1:
            length = pow(2,i+1) - pow(2,i)
            if i % 2 == 0: 
                prev = [j for j in range(int(pow(2,i)-1),int(pow(2,i-1)-1),-1)]
                idx = int((label%length)/2)
            
            else:
                prev = [j for j in range(int(pow(2,i-1)),int(pow(2,i)))]
                idx = int((length -1 - (label % length))/2)
                
            label = prev[idx]
            ans.append(label)
            i = math.floor(math.log(label,2))
        return ans[::-1]


import numpy as np
class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        def findCounterpart(num: int) -> int:
            pow_flr = int(np.floor(np.log2(num)))
            layer = list(range(2 ** pow_flr, 2 ** (pow_flr + 1)))
            return layer[-layer.index(num)-1]
        res = [label]
        now = label
        while now != 1:
            now = findCounterpart(now // 2)
            res.insert(0, now)
        return res

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        h = 1
        symmetry = [2]
        while 2**h - 1 < label//2:
            symmetry.append(symmetry[-1]*2 + 1)
            h += 1
        path = [label]
        while label > 1:
            parent = label >> 1
            label = symmetry[-1] - parent
            path.append(label)
            symmetry.pop()
        return reversed(path)


import math

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        current = label
        res = [current]
        
        while current != 1:
            current //= 2
            depth = int(math.log2(current))
            
            nodes = [i for i in range(2**depth, 2**(depth+1))]
            
            idx = nodes.index(current)
            current = list(reversed(nodes))[idx]
            res.append(current)
            
        return reversed(res)
            
            
            
            
            
            


import math

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        req_length = math.ceil(math.log(label+1, 2))
        curr_depth = req_length
        next_depth = curr_depth-1
        res = []
        
        while len(res) != req_length-1:
            
            res.insert(0, label)
            
            curr_numbers = list(range(2**(curr_depth-1), 2**curr_depth))
            next_numbers = list(range(2**(next_depth-1), 2**next_depth))
                                
            if curr_depth%2 == 0:
                curr_numbers.reverse()
            
            if next_depth%2 == 0:
                next_numbers.reverse()
            
            # print(curr_numbers, next_numbers)
            
            label = next_numbers[curr_numbers.index(label)//2]
            curr_depth -= 1
            next_depth -= 1
        res.insert(0, 1)
        return res  


class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        ans = [label]
        i = int(math.log(label,2))
        while i >= 1:
            length = pow(2,i+1) - pow(2,i)
            if i % 2 == 0: 
                prev = [j for j in range(int(pow(2,i)-1),int(pow(2,i-1)-1),-1)]
                idx = int((label%length)/2)
            
            else:
                prev = [j for j in range(int(pow(2,i-1)),int(pow(2,i)))]
                idx = int((length -1 - (label % length))/2)
                
            label = prev[idx]
            ans.append(label)
            i = int(math.log(label,2))
        ans.sort()
        return ans


import math

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        ret = [label]
        
        while label != 1:
            level = math.floor(math.log2(label))
            
            max_at_level = 2**(level+1) - 1
            
            label = ((max_at_level - label) // 2) + 2**(level - 1)
            ret.append(label)
            
        return reversed(ret)

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        i=label
        lst=[]
        while(i>=1):
            lst.append(i)
            i=i//2
        n=len(lst)
        lst=lst[::-1]
        print(lst)
        for i in range(n):
            if n%2==1:
                if i%2==1:
                    lst[i]=(2**i)+(2**(i+1))-1-lst[i]
            else:
                if i%2==0:
                    lst[i]=(2**i)+(2**(i+1))-1-lst[i]
        return lst


class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        x=bin(label)[2:]
        n = len(x)
        #invert path
        y=\"1\"
        for i in range(1, n): y += \"0\" if x[i] == \"1\" else \"1\"
        #Follow path in odd even fashion
        out = []
        for i in range(n):
            if n%2 == 0:
                if i % 2 == 1: out.append(int(x[:i+1], 2))
                else: out.append(int(y[:i+1], 2))
            else:
                if i % 2 == 0: out.append(int(x[:i+1], 2))
                else: out.append(int(y[:i+1], 2))
        return out

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        if label==1:
            return [1]
        #else:
        ans = []
        for i in range(50):
            if (2**i<=label)and(2**(i+1)-1>=label):
                break
            #print(i)
        if i % 2 ==1:
            label = 2**i + 2**(i+1) -1 - label
        #print(label)
        x=label
        for j in range(i,-1,-1):
            if j % 2 ==1:
                ans.append(2**j + 2**(j+1) -1 - x)
            else:
                ans.append(x)
            x = x // 2
            
            
        return ans[::-1] 
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            
            


class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        from math import floor, log
        def pos2num(row, pos):
            if row %2 == 0:
                return 2**row + pos
            else:
                return 2**(row+1) - pos - 1
        targetrow = floor(log(label)/log(2))
        if targetrow %2 == 0:
            targetpos = label - 2**targetrow
        else:
            targetpos = 2**(targetrow+1) - label -1
        row = 0
        out = []
        offset = 0
        posoffset = 0
        while row <= targetrow:
            out.append(pos2num(row, posoffset))
            posoffset *=2
            if targetpos < offset + 2**(targetrow - row - 1):
                #go left
                pass
            else:
                #go right
                offset += 2**(targetrow - row - 1)
                posoffset +=1
            #out.append(pos2num(row, offset))
            row +=1
        return out


class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        x=bin(label)[2:]
        n = len(x)
        out = []
        y=\"1\"
        for i in range(1,n):
            y+=\"0\" if x[i]==\"1\" else \"1\"
        for i in range(n):
            if n%2==0:
                if i%2==1: out.append(int(x[:i+1],2))
                else: out.append(int(y[:i+1],2))
            else:
                if i%2==0: out.append(int(x[:i+1],2))
                else: out.append(int(y[:i+1],2))
        return out

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        level = int(math.log2(label))
        res, count = [], 0
        while label > 0:
            res.append(label if count % 2 == 0 else (3 * 2 ** level - 1 - label))
            label >>= 1
            level -= 1
            count += 1
            
        return res[::-1]