LC 1104 [M] Path In Zigzag Labelled Binary Tree - ALawliet/algorithms GitHub Wiki

this is more a math problem than a tree problem with the formulas:

level_min = 2**(level-1)
level_max = 2**(level) - 1
label = int((level_min + level_max - label) / 2)

class Solution:
    def pathInZigZagTree(self, label):
        res = [] # O(log n) space
        node_count = 1
        level = 1
        
        # Determine level of the label
        
        # while label >= node_count*2: # O(log n) time
        while label > 2**(level) - 1: # level max
            # node_count *= 2
            level += 1
            
        # Iterate from the target label to the root
        while label != 0: # O(log n) time
            res.append(label)
            
            level_min = 2**(level-1)
            level_max = 2**(level) - 1
            print(f'{level}: {level_min}-{level_max} ({label})')
            label = int((level_min + level_max - label) / 2) # next label at next level
            print(f'jump label {label}')
            
            level -= 1
            
        return res[::-1] # O(n) time