Zig Zag or Spiral Traversal
M2P FintechThe problem
Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
Input : root = [1, 2, 3, null, 4, 8, 5] Output : [ [1] , [3, 2], [4, 8, 5] ] Explanation : So at root we move from left to right. At next level we move in opposite direction i.e. from right to left. At next level again reverse the traversal i.e. from left to right.
Input : root = [3, 9, 20, null, null, 15, 7] Output : [ [3] , [20, 9], [15, 7] ] Explanation : So at root we move from left to right. At next level we move in opposite direction i.e. from right to left , from 20 to 9. At next level again reverse the traversal i.e. from left to right, from 15 to 7.
Input : root = [5, 1, 2, 8, null, 4, 5, null, 6]
- 1 <= Number of Nodes <= 104
- -103 <= Node.val <= 103
cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
class Solution {
public:
vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
//your code goes here
}
};java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int data;
* TreeNode left;
* TreeNode right;
* TreeNode(int val) { data = val; left = null, right = null }
* }
**/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
//your code goes here
}
}python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def zigzagLevelOrder(self, root):
#your code goes herejavascript
/**
* Definition for a binary tree node.
* class TreeNode {
* constructor(val = 0, left = null, right = null){
* this.data = val;
* this.left = null;
* this.right = null;
* }
* }
**/
class Solution {
zigzagLevelOrder(root) {
//your code goes here
}
}csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int data;
* public TreeNode left;
* public TreeNode right;
* TreeNode(int val) { data = val; left = null, right = null }
* }
*/
public class Solution {
public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
//your code goes here
}
}go
/*
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
*/
func zigzagLevelOrder(root *TreeNode) [][]int {
//your code goes here
}Stuck? Show a way to structure it+
- 01Process one queue level at a time.
- 02Allocate a result row of that level's size.
- 03Write each value at normal or reversed index based on direction.
- 04Flip direction after every level.
Reference answer
Then expect these follow-ups
How would a deque avoid indexed row writes?
Tests: deque usage
How is spiral traversal of a graph different?
Tests: tree assumptions
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question