Path In Zigzag Labelled Binary Tree — LeetCode 1104 Python Solution

The problem

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.

Example

Input

label = 14

Output

[1,3,4,14]

Python solution

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        x = i = 1
        while (x << 1) <= label:
            x <<= 1
            i += 1
        ans = [0] * i
        while i:
            ans[i - 1] = label
            label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1
            i -= 1
        return ans

Complexity

Pattern: Tree Traversal

Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1104. Path In Zigzag Labelled Binary Tree is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Tree and Binary Tree.

The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.

Related problems