1104. Path In Zigzag Labelled Binary Tree LeetCode Solution

In this guide, you will get 1104. Path In Zigzag Labelled Binary Tree LeetCode Solution with the best time and space complexity. The solution to Path In Zigzag Labelled Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Path In Zigzag Labelled Binary Tree solution in C++
4. Path In Zigzag Labelled Binary Tree solution in Java
5. Path In Zigzag Labelled Binary Tree solution in Python
6. Additional Resources

Problem Statement of 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

Complexity Analysis

• Time Complexity:
• Space Complexity:

1104. Path In Zigzag Labelled Binary Tree LeetCode Solution in C++

class Solution {
 public:
  vector<int> pathInZigZagTree(int label) {
    deque<int> ans;
    int level;

    for (int l = 0; l < 21; ++l)
      if (pow(2, l) > label) {
        level = l - 1;
        break;
      }

    if (level % 2 == 1)
      label = boundarySum(level) - label;

    for (int l = level; l >= 0; --l) {
      ans.push_front(l % 2 == 0 ? label : boundarySum(l) - label);
      label /= 2;
    }

    return {ans.begin(), ans.end()};
  }

 private:
  int boundarySum(int level) {
    return pow(2, level) + pow(2, level + 1) - 1;
  }
};
/* code provided by PROGIEZ */

1104. Path In Zigzag Labelled Binary Tree LeetCode Solution in Java

class Solution {
  public List<Integer> pathInZigZagTree(int label) {
    LinkedList<Integer> ans = new LinkedList<>();
    int level = 0;

    for (int l = 0; l < 21; ++l)
      if (Math.pow(2, l) > label) {
        level = l - 1;
        break;
      }

    if (level % 2 == 1)
      label = boundarySum(level) - label;

    for (int l = level; l >= 0; --l) {
      ans.addFirst(l % 2 == 0 ? label : boundarySum(l) - label);
      label /= 2;
    }

    return new ArrayList<>(ans);
  }

  private int boundarySum(int level) {
    return (int) Math.pow(2, level) + (int) Math.pow(2, level + 1) - 1;
  }
}
// code provided by PROGIEZ

1104. Path In Zigzag Labelled Binary Tree LeetCode Solution in Python

class Solution:
  def pathInZigZagTree(self, label: int) -> list[int]:
    def boundarySum(level: int):
      return 2**level + 2**(level + 1) - 1

    ans = []

    for l in range(21):
      if 2**l > label:
        level = l - 1
        break

    if level % 2 == 1:
      label = boundarySum(level) - label

    for l in reversed(range(level + 1)):
      ans.append(label if l % 2 == 0 else boundarySum(l) - label)
      label //= 2

    return ans[::-1]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.