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&nbsp;node with that label.

&nbsp;
Example 1:

Input: label = 14
Output: [1,3,4,14]


Example 2:

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


&nbsp;
Constraints:


	1 &lt;= label &lt;= 10^6


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

        #determine level of label
        #O(log n)
        level, nodeCount = 1, 1
        while label >= nodeCount * 2:
            nodeCount *= 2
            level += 1

        #Olog(n) time
        while label > 1:
            #compute max and min node
            maxNode, minNode = 2**level-1, 2**(level-1)

            parent = ((maxNode + minNode) - label) // 2

            #slightly costly operation
            result = [parent] + result

            label = parent
            level -= 1

        return result
class Solution {
    
   
    
    
    public List<Integer> pathInZigZagTree(int label) 
    {
        int level, upper, parent, i = label;
        double min, max;
        List<Integer> ans = new ArrayList<Integer> ();
        
        ans.add(i);
        
        while( i> 1)
        {
            level = (int)(Math.log(i) / Math.log(2));
            upper = level -1;
            min = Math.pow(2.0, upper);
            max = Math.pow(2.0, level) - 1;
            parent = (int)(min + max) - i/2; 
            
            ans.add(0, parent);
            i = parent;
        }
        
        return ans;
        
        
    }
}
class Solution
{
public:
    vector<int> pathInZigZagTree(int label)
    {
        vector<int> v;
        int n = 0, num = label;
        while (label)
        {
            n++;
            label = label >> 1;
        }

        int l, r, c, ans;
        for (int i = n; i >= 2; i--)
        {

            r = pow(2, i) - 1;
            l = pow(2, i - 1);
            c = r - num;
            ans = l + c;
            if ((n + i) % 2)
            {
                v.push_back(ans);
            }
            else
            {
                v.push_back(num);
            }
            num /= 2;
        }
        v.push_back(1);
        sort(v.begin(), v.end());
        return v;
    }
};
var pathInZigZagTree = function(label) {
    //store highest and lowest value for each level
    let levels = [[1,1]] //to reduce space complexity we will fill the levels array with out output as we go
    let totalNodes = 1
    let nodesInLastRow = 1
    
    //Calculate which level the label lies in
    while (totalNodes < label) {      
        let lowest = totalNodes + 1
        
        nodesInLastRow = nodesInLastRow * 2
        totalNodes += nodesInLastRow
          
        let highest = totalNodes
        
        levels.push([lowest, highest])
    }
    

    let index = levels.length
    let childBoundaries = levels[levels.length -1]
    levels[levels.length -1] = label
    
    //Work bottom up, for each level, calculate the value based on the child and the child boundaries boundaries
    for (let i=levels.length-2; i>=0; i--) {
        let childLevel = i+2 //2 because i is index of 0, so 1 is to preset it to 1...n and then and second one is parent level
        let childValue = levels[i+1]    
        
        let inversionCalculation = Math.abs((childBoundaries[0] + childBoundaries[1]) - childValue)
        
        childBoundaries = levels[i]
        
        levels[i] = Math.floor(inversionCalculation/2)   
    }
    
    return levels
};
Path In Zigzag Labelled Binary Tree