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.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.
 
Example 1:
Input: label = 14
Output: [1,3,4,14]

Example 2:
Input: label = 26
Output: [1,2,6,10,26]

 
Constraints:

1 <= label <= 10^6

Source: leetcode | Difficulty: MEDIUM
Tags: Tree algorithms

Mathematics

Starter code: class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        

Solutions:
class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:
		res = []
		level = 0
		nodes_count = 0
		while nodes_count < label:
			nodes_count += 2 ** level
			level += 1
		while label != 0:
			res.append(label)
			level_max = 2 ** level - 1
			level_min = 2 ** (level - 1)
			label = (level_max + level_min - label) // 2
			level -= 1
		return res[::-1]


import math

class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:
		res = []
		level = math.ceil(math.log(label + 1, 2))
		res.append(label)
		if level % 2 == 1:
			label = label // 2
			level -= 1
			label = abs(pow(2, level) - label) + pow(2, level - 1) - 1
			res.append(label)
		while label >= 1:
			if level % 2 == 1:
				level -= 1
				label = label // 2
				res.append(label)
			else:
				label = label // 2
				level -= 1
				res.append(abs(pow(2, level) - label) + pow(2, level - 1) - 1)
		res.pop()
		return res[::-1]


import math

class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:

		def findIndexorLabel(value):
			level = int(math.log(value, 2)) + 1
			if level % 2:
				index = value
			else:
				total = 2 ** (level - 1) + (2 ** level - 1)
				index = total - value
			return index
		arr = []
		arr.insert(0, label)
		index = findIndexorLabel(label)
		parentNode = index // 2
		while parentNode != 0:
			nodeVal = findIndexorLabel(parentNode)
			arr.insert(0, nodeVal)
			index = findIndexorLabel(nodeVal)
			parentNode = index // 2
		return arr


class Solution:

	def pathInZigZagTree(self, label: int):
		out = []
		while label >= 1:
			out.append(label)
			label = self.swap(label)
		return out[::-1]

	def swap(self, x):
		to = 1
		while to <= x:
			to = to << 1
		return (to + (to >> 1) - 1 - x) // 2


import numpy as np

class Solution:

	def parent(self, label: int) -> int:
		row = int(np.log2(label))
		counter = label - 2 ** row
		parent = label - (counter + int(counter / 2) + 1)
		return parent

	def pathInZigZagTree(self, label: int) -> List[int]:
		sol = []
		while True:
			sol.append(label)
			print(sol)
			if label > 1:
				label = Solution.parent(self, label)
			else:
				break
		return sol[::-1]


class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:
		n = label
		change = False
		stack = []
		index = -1
		while n > 0:
			stack.append(n)
			n = int(n / 2)
			index += 1
		check = False
		output = []
		while stack:
			p = stack.pop(0)
			if not check:
				output.append(p)
			else:
				start = pow(2, index)
				end = pow(2, index + 1) - 1
				while start <= end:
					if p == start:
						output.append(end)
						break
					elif p == end:
						output.append(start)
						break
					start += 1
					end -= 1
			check = not check
			index -= 1
		return output[::-1]


class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:
		ans = [label]
		i = math.floor(math.log(label, 2))
		while i >= 1:
			length = pow(2, i + 1) - pow(2, i)
			if i % 2 == 0:
				prev = [j for j in range(int(pow(2, i) - 1), int(pow(2, i - 1) - 1), -1)]
				idx = int(label % length / 2)
			else:
				prev = [j for j in range(int(pow(2, i - 1)), int(pow(2, i)))]
				idx = int((length - 1 - label % length) / 2)
			label = prev[idx]
			ans.append(label)
			i = math.floor(math.log(label, 2))
		return ans[::-1]


import numpy as np

class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:

		def findCounterpart(num: int) -> int:
			pow_flr = int(np.floor(np.log2(num)))
			layer = list(range(2 ** pow_flr, 2 ** (pow_flr + 1)))
			return layer[-layer.index(num) - 1]
		res = [label]
		now = label
		while now != 1:
			now = findCounterpart(now // 2)
			res.insert(0, now)
		return res


class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:
		h = 1
		symmetry = [2]
		while 2 ** h - 1 < label // 2:
			symmetry.append(symmetry[-1] * 2 + 1)
			h += 1
		path = [label]
		while label > 1:
			parent = label >> 1
			label = symmetry[-1] - parent
			path.append(label)
			symmetry.pop()
		return reversed(path)


import math

class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:
		current = label
		res = [current]
		while current != 1:
			current //= 2
			depth = int(math.log2(current))
			nodes = [i for i in range(2 ** depth, 2 ** (depth + 1))]
			idx = nodes.index(current)
			current = list(reversed(nodes))[idx]
			res.append(current)
		return reversed(res)


import math

class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:
		req_length = math.ceil(math.log(label + 1, 2))
		curr_depth = req_length
		next_depth = curr_depth - 1
		res = []
		while len(res) != req_length - 1:
			res.insert(0, label)
			curr_numbers = list(range(2 ** (curr_depth - 1), 2 ** curr_depth))
			next_numbers = list(range(2 ** (next_depth - 1), 2 ** next_depth))
			if curr_depth % 2 == 0:
				curr_numbers.reverse()
			if next_depth % 2 == 0:
				next_numbers.reverse()
			label = next_numbers[curr_numbers.index(label) // 2]
			curr_depth -= 1
			next_depth -= 1
		res.insert(0, 1)
		return res


import math

class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:
		ret = [label]
		while label != 1:
			level = math.floor(math.log2(label))
			max_at_level = 2 ** (level + 1) - 1
			label = (max_at_level - label) // 2 + 2 ** (level - 1)
			ret.append(label)
		return reversed(ret)


class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:
		i = label
		lst = []
		while i >= 1:
			lst.append(i)
			i = i // 2
		n = len(lst)
		lst = lst[::-1]
		print(lst)
		for i in range(n):
			if n % 2 == 1:
				if i % 2 == 1:
					lst[i] = 2 ** i + 2 ** (i + 1) - 1 - lst[i]
			elif i % 2 == 0:
				lst[i] = 2 ** i + 2 ** (i + 1) - 1 - lst[i]
		return lst


class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:
		if label == 1:
			return [1]
		ans = []
		for i in range(50):
			if 2 ** i <= label and 2 ** (i + 1) - 1 >= label:
				break
		if i % 2 == 1:
			label = 2 ** i + 2 ** (i + 1) - 1 - label
		x = label
		for j in range(i, -1, -1):
			if j % 2 == 1:
				ans.append(2 ** j + 2 ** (j + 1) - 1 - x)
			else:
				ans.append(x)
			x = x // 2
		return ans[::-1]


class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:
		from math import floor, log

		def pos2num(row, pos):
			if row % 2 == 0:
				return 2 ** row + pos
			else:
				return 2 ** (row + 1) - pos - 1
		targetrow = floor(log(label) / log(2))
		if targetrow % 2 == 0:
			targetpos = label - 2 ** targetrow
		else:
			targetpos = 2 ** (targetrow + 1) - label - 1
		row = 0
		out = []
		offset = 0
		posoffset = 0
		while row <= targetrow:
			out.append(pos2num(row, posoffset))
			posoffset *= 2
			if targetpos < offset + 2 ** (targetrow - row - 1):
				pass
			else:
				offset += 2 ** (targetrow - row - 1)
				posoffset += 1
			row += 1
		return out


class Solution:

	def pathInZigZagTree(self, label: int) -> List[int]:
		level = int(math.log2(label))
		(res, count) = ([], 0)
		while label > 0:
			res.append(label if count % 2 == 0 else 3 * 2 ** level - 1 - label)
			label >>= 1
			level -= 1
			count += 1
		return res[::-1]