1104. Path In Zigzag Labelled Binary Tree #

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.

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

Problem Summary #

In an infinite binary tree, every node has two children, and the nodes in the tree are labelled row by row in a “zigzag” pattern. As shown in the figure below, in odd-numbered rows (that is, the first row, third row, fifth row, …), labels are assigned from left to right; while in even-numbered rows (that is, the second row, fourth row, sixth row, …), labels are assigned from right to left.

Given the label label of a node in the tree, return the path from the root node to the node with label label, consisting of the labels of the nodes along the way.

Solution Approach #

• Calculate the level and index where label is located.
• Calculate the parent node’s index and value based on the index and level.
• Decrease the level by one, and repeatedly calculate the corresponding parent node until reaching the root node.

Code #

package leetcode

func pathInZigZagTree(label int) []int {
	level := getLevel(label)
	ans := []int{label}
	curIndex := label - (1 << level)
	parent := 0
	for level >= 1 {
		parent, curIndex = getParent(curIndex, level)
		ans = append(ans, parent)
		level--
	}
	ans = reverse(ans)
	return ans
}

func getLevel(label int) int {
	level := 0
	nums := 0
	for {
		nums += 1 << level
		if nums >= label {
			return level
		}
		level++
	}
}

func getParent(index int, level int) (parent int, parentIndex int) {
	parentIndex = 1<<(level-1) - 1 + (index/2)*(-1)
	parent = 1<<(level-1) + parentIndex
	return
}

func reverse(nums []int) []int {
	left, right := 0, len(nums)-1
	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
	return nums
}