<p>In an infinite binary tree where every node has two children, the nodes are labelled in row order.</p>

<p>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.</p>

<p><img alt="" src="https://assets.leetcode.com/uploads/2019/06/24/tree.png" style="width: 300px; height: 138px;" /></p>

<p>Given the <code>label</code> of a node in this tree, return the labels in the path from the root of the tree to the&nbsp;node with that <code>label</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> label = 14
<strong>Output:</strong> [1,3,4,14]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> label = 26
<strong>Output:</strong> [1,2,6,10,26]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= label &lt;= 10^6</code></li>
</ul>

from typing import List

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        # Initialize the level to 1 and the start value of that level (x) to 1.
        level = 1
        startOfLevel = 1

        # Determine the level of the tree where the label is located.
        while (startOfLevel * 2) <= label:
            startOfLevel *= 2
            level += 1

        # Create a list to store the path from root to the label.
        path = []

        # Starting from the label's level, move up to the root.
        for currentLevel in range(level, 0, -1):
            # Add the current label to the path.
            path.append(label)

            # Calculate the parent label in the previous level of a perfect binary tree,
            # then adjust for the zigzag pattern.
            levelStart = (1 << (currentLevel - 1)) # Start of the current level
            levelEnd = (1 << currentLevel) - 1 # End of the current level
            label = (levelStart + levelEnd - label) // 2

        # Since we've built the path from the bottom up, reverse it to get the correct order.
        path.reverse()

        return path

16500