{x}
blog image

Path In Zigzag Labelled Binary Tree

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

Solution Explanation: Path In Zigzag Labelled Binary Tree

This problem involves traversing a uniquely labeled binary tree. The labeling follows a zigzag pattern: odd-numbered rows are labeled left-to-right, and even-numbered rows are labeled right-to-left. The goal is to find the path from the root (label 1) to a given node label.

Approach:

The solution leverages mathematical properties of the tree's structure to efficiently determine the path without explicitly building the tree. The key observations are:

  1. Row Calculation: The row number (i) of a given label can be determined by repeatedly doubling a counter (x) until it exceeds or equals the label. This efficiently locates the row without iterating through all rows.

  2. Complementary Node: In each row, a node's position relative to the row's start is mirrored in the next row. For example, if a node is the second element from the left in an even row, its parent in the previous odd row will be the second element from the right. This is captured by the calculation ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1.

  3. Parent Node: The parent's label is found by calculating the complementary node's label (as described above) and dividing by 2. This uses bit manipulation (>> 1) for efficient division by 2.

  4. Path Construction: By iteratively calculating the parent node, we work our way up from the given label to the root (label 1). The path is then reversed since the problem requires the path from root to leaf.

Time Complexity: O(log n), where n is the input label. This is because the algorithm iterates up the tree, and the height of the tree is logarithmic with respect to the number of nodes.

Space Complexity: O(log n) to store the path (though this can be considered O(1) if ignoring the space for the output).

Code Explanation (Python):

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        x = i = 1
        while (x << 1) <= label:  # Find row number (i) using bitwise left shift
            x <<= 1
            i += 1
        ans = [0] * i  # Initialize path array with size equal to the row number
        while i:  # Iterate from the given label upwards to the root
            ans[i - 1] = label  # Add the current label to the path
            label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1  #Calculate the parent label
            i -= 1
        return ans  # Return the path (already in correct order from root to leaf)

The code in other languages (Java, C++, Go) follows the same logic, differing only in syntax and data structures. The core mathematical calculations remain consistent across all implementations.