10. ZigZag Tree Traversal
✅ GFG solution to the ZigZag Tree Traversal problem: perform level order traversal in alternating left-to-right and right-to-left directions using efficient queue-based techniques. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
Given the root of a binary tree, you need to perform a zigzag level order traversal. In this traversal:
Odd-numbered levels (1st, 3rd, 5th, etc.) are traversed from left to right.
Even-numbered levels (2nd, 4th, 6th, etc.) are traversed from right to left.
Return the nodes in the order they appear during this zigzag traversal.
📘 Examples
Example 1
Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [1, 3, 2, 4, 5, 6, 7]
Explanation:
Level 1 (left to right): [1]
Level 2 (right to left): [3, 2]
Level 3 (left to right): [4, 5, 6, 7]
Final result: [1, 3, 2, 4, 5, 6, 7]Example 2
Input: root = [7, 9, 7, 8, 8, 6, N, 10, 9]
Output: [7, 7, 9, 8, 8, 6, 9, 10]
Explanation:
Level 1 (left to right): [7]
Level 2 (right to left): [7, 9]
Level 3 (left to right): [8, 8, 6]
Level 4 (right to left): [9, 10]
Final result: [7, 7, 9, 8, 8, 6, 9, 10]🔒 Constraints
$1 \le \text{number of nodes} \le 10^5$
$1 \le \text{node->data} \le 10^5$
✅ My Approach
The optimal approach uses Queue-Based Level Order Traversal with Index Manipulation to achieve zigzag ordering efficiently:
Queue with Index Positioning
Initialize Data Structures:
Use a queue for standard level-order traversal (BFS).
Maintain a boolean flag
ltr(left-to-right) to track current direction.Create result vector to store final traversal order.
Process Each Level:
For each level, determine its size to process all nodes at current depth.
Create a temporary level vector of the exact size needed.
Smart Index Placement:
For left-to-right levels: place nodes at their natural index position (0, 1, 2, ...).
For right-to-left levels: place nodes at reversed index positions (size-1, size-2, ...).
This eliminates the need for explicit reversal operations.
Add Children to Queue:
Always add left child first, then right child (standard BFS order).
The queue maintains proper level-by-level traversal regardless of zigzag pattern.
Toggle Direction:
After processing each level, flip the
ltrflag.Append the level vector to result and continue to next level.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n), where n is the number of nodes in the binary tree. Each node is visited exactly once during the level order traversal, and inserting nodes at calculated indices takes constant time.
Expected Auxiliary Space Complexity: O(w), where w is the maximum width of the tree. The queue stores at most one complete level of nodes at any given time, which in the worst case (complete binary tree) is approximately n/2 nodes at the last level.
🧑💻 Code (C++)
class Solution {
public:
vector<int> zigZagTraversal(Node* root) {
vector<int> res;
if (!root) return res;
queue<Node*> q;
q.push(root);
bool ltr = true;
while (!q.empty()) {
int sz = q.size();
vector<int> lvl(sz);
for (int i = 0; i < sz; i++) {
Node* node = q.front();
q.pop();
int idx = ltr ? i : sz - 1 - i;
lvl[idx] = node->data;
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
ltr = !ltr;
res.insert(res.end(), lvl.begin(), lvl.end());
}
return res;
}
};☕ Code (Java)
class Solution {
ArrayList<Integer> zigZagTraversal(Node root) {
ArrayList<Integer> res = new ArrayList<>();
if (root == null) return res;
Queue<Node> q = new LinkedList<>();
q.add(root);
boolean ltr = true;
while (!q.isEmpty()) {
int sz = q.size();
Integer[] lvl = new Integer[sz];
for (int i = 0; i < sz; i++) {
Node node = q.poll();
int idx = ltr ? i : sz - 1 - i;
lvl[idx] = node.data;
if (node.left != null) q.add(node.left);
if (node.right != null) q.add(node.right);
}
ltr = !ltr;
Collections.addAll(res, lvl);
}
return res;
}
}🐍 Code (Python)
class Solution:
def zigZagTraversal(self, root):
res = []
if not root: return res
q = deque([root])
ltr = True
while q:
sz = len(q)
lvl = [0] * sz
for i in range(sz):
node = q.popleft()
idx = i if ltr else sz - 1 - i
lvl[idx] = node.data
if node.left: q.append(node.left)
if node.right: q.append(node.right)
ltr = not ltr
res.extend(lvl)
return res🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated