Path in Zigzag Labelled Binary Tree in Python

Suppose in an infinite binary tree where every node has two children, the nodes are labelled in row order. Now in the odd numbered rows (the first, third, fifth,...), the labelling is left to right, and in the even numbered rows (second, fourth, sixth,...), the labelling is right to left. So the tree will be like −

So we have given the label of a node in this tree, we have to find the labels in the path from the root of the tree to the node with that label. So if the input is label = 14, then the output will be [1,3,4,14]

To solve this, we will follow these steps −

• Define two array tree and res, insert 0 and 1 into the tree array, set odd := 1 and current := 1 and two := 2

• if label = 1, then return a list with single element 1.

• Create one infinite loop −

  • if odd is non-zero, then

    • max_val := current + two

    • temp := max_val

    • while temp > current

      • insert temp into tree

      • if temp = label, then come out from the loop

      • decrease temp by 1

    • if last element of tree is label, then come out from the loop

    • current := max_val

  • otherwise

    • temp := two

    • while temp is not zero

      • temp := 1, increase current by 1, then increase current into tree

      • if current = label, then come out form the loop

    • if last element of tree is label, then come out from the loop

  • temp := temp * 2

  • odd := false if odd is non zero, otherwise true

• index := length of tree – 1

• while index is not 0

  • insert tree[index] into res array

  • index := index / 2

• res := reversed list of res

• return res

Example(Python)

Let us see the following implementation to get a better understanding −

 Live Demo

class Solution(object):
   def pathInZigZagTree(self, label):
      tree = []
      res = []
      tree.append(0)
      tree.append(1)
      odd = 1
      current = 1
      two = 2
      if label == 1:
         return [1]
      while True:
         if odd:
            max_val = current + two
            temp = max_val
            while temp>current:
               tree.append(temp)
               if temp == label:
                  break
               temp-=1
            if tree[-1]== label:
               break
            current = max_val
         else:
            temp = two
            while temp:
               temp-=1
               current+=1
               tree.append(current)
            if current == label:
               break
            if tree[-1]== label:
               break
         two*=2
         odd = not odd
      index = len(tree)-1
      while index:
         res.append(tree[index])
         index//=2
      res=res[::-1]
      return res
ob = Solution()
print(ob.pathInZigZagTree(14))

Input

14

Output

[1,3,4,14]