We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Path In Zigzag Labelled Binary Tree

Number: 1194

Difficulty: Medium

Paid? No

Companies: Bloomberg

Problem Description

Given a label for a node in an infinite binary tree where nodes are labelled in row order with alternating directions (left-to-right for odd levels and right-to-left for even levels), return the sequence of labels along the path from the root to the given node.

Key Insights

  • The tree is a complete binary tree with levels labelled sequentially.
  • The labelling is zigzag: levels with even numbers reverse the order.
  • Determine the level of the given label using logarithms.
  • Convert the label to its corresponding value in a standard complete binary tree by "mirroring" the value when in an even level.
  • Compute the parent in the standard tree, then reverse the conversion to get the parent in the zigzag tree.
  • Iterate from the given label back to the root and finally reverse the collected path.

Space and Time Complexity

Time Complexity: O(log(label)) since the number of levels is proportional to the logarithm of the label. Space Complexity: O(log(label)) to store the path from the node to the root.

Solution

The solution involves converting the node label in the zigzag tree to its corresponding label in a normally labelled complete binary tree and then computing the parent node. For any node, its level is found using the logarithm (base 2). When the level is even, the label is mirrored within the range of labels of that level (calculated using the minimum and maximum available labels in that level). The parent's label in the normal tree is then calculated by integer division by 2, and if applicable, we mirror it back to the zigzag format for the next level. This process repeats until reaching the root, and then the path is reversed to provide the root-to-node order. The algorithm primarily uses simple arithmetic and logarithmic operations.

Code Solutions

import math

def pathInZigZagTree(label):
    # Initialize path container
    path = []
    # Iterate until label becomes 0 (we have reached above the root)
    while label:
        # Append current label to the path
        path.append(label)
        # Determine the level of the current label.
        level = int(math.floor(math.log(label, 2))) + 1
        # Calculate the start and end of this level in a normal complete binary tree.
        level_start = 2 ** (level - 1)
        level_end = 2 ** level - 1
        # Mirror the label in the current level (only needed if the level is even)
        label = (level_start + level_end - label) // 2
    # Reverse the collected path to get the sequence from the root to the target label.
    return path[::-1]

# Example usage:
print(pathInZigZagTree(14))  # Output: [1, 3, 4, 14]
print(pathInZigZagTree(26))  # Output: [1, 2, 6, 10, 26]
← Back to All Questions