Path In Zigzag Labelled Binary Tree

Problem Id: 1104 Difficulty: Medium Tag: Math Tag: Tree


Intuition

We could get the value of parent of a node, by handling with its binary format.

E.g. bin(26) = '0b11010', its parent is '0b1010'. Notice that to get x's parent we need to first get x >> 1, then, negate it except for the first number.

Solution


class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        res = []
        depth = 0
        while 2 ** depth <= label:
            depth += 1
        depth -= 1

        while label:
            res.append(label)
            # Calculate parent of label
            depth -= 1
            mod = 2 ** depth
            label = (mod - 1) - (label - mod) + mod
        return res