Solution For Binary Tree Zigzag Level Order Traversal
Binary Tree Zigzag Level Order Traversal is a problem on LeetCode that requires us to find the zigzag level order traversal of a binary tree. In other words, we need to traverse the binary tree level by level, alternating the direction we go from left to right and right to left at each level.
To solve this problem, we will use a queue to keep track of the nodes in each level of the binary tree. We will also use a variable to keep track of whether we are currently traversing the level from left to right or from right to left.
Here is the step-by-step algorithm to solve the Binary Tree Zigzag Level Order Traversal problem:
Create an empty list called result, which will hold the zigzag level order traversal of the binary tree.
Create an empty queue called levelQueue, which will hold the nodes in the current level of the binary tree.
Create a variable called leftToRight, which will initially be set to True to indicate that we are currently traversing the first level from left to right.
Enqueue the root node of the binary tree into the levelQueue.
While the levelQueue is not empty, do the following:
a. Create a list called levelNodes, which will hold the nodes in the current level of the binary tree.
b. Get the size of the levelQueue and loop through it that many times. During each iteration, dequeue a node from the levelQueue and append it to the levelNodes list.
c. If leftToRight is True, reverse the order of the nodes in the levelNodes list.
d. Append the levelNodes list to the result list.
e. Loop through the nodes in the levelNodes list and enqueue their left and right children (if they exist) into the levelQueue.
f. Toggle the value of leftToRight to switch the direction of traversal for the next level.
- Return the result list, which now contains the zigzag level order traversal of the binary tree.
Here is the Python code implementation of the above algorithm:
“`
def zigzagLevelOrder(root):
if not root:
return []
result = []
levelQueue = [root]
leftToRight = True
while levelQueue:
levelNodes = []
size = len(levelQueue)
for i in range(size):
node = levelQueue.pop(0)
levelNodes.append(node)
if node.left:
levelQueue.append(node.left)
if node.right:
levelQueue.append(node.right)
if not leftToRight:
levelNodes.reverse()
result.append([node.val for node in levelNodes])
leftToRight = not leftToRight
return result
“`
The above code takes O(N) time and O(N) space complexity, where N is the number of nodes in the binary tree.
Step by Step Implementation For Binary Tree Zigzag Level Order Traversal
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List> zigzagLevelOrder(TreeNode root) {
//Create a list to store the final output
List> result = new ArrayList<>();
//Check for base case
if(root == null) {
return result;
}
//Create a queue to do BFS
Queue queue = new LinkedList<>();
queue.add(root);
boolean flag = true; //Flag to indicate the order in which nodes should be added to the list
//Do BFS
while(!queue.isEmpty()) {
//Create a list to store nodes at a particular level
List temp = new ArrayList<>();
int size = queue.size();
for(int i = 0; i < size; i++) {
TreeNode curr = queue.remove();
if(flag) {
temp.add(curr.val);
}
else {
temp.add(0, curr.val);
}
if(curr.left != null) {
queue.add(curr.left);
}
if(curr.right != null) {
queue.add(curr.right);
}
}
result.add(temp);
flag = !flag;
}
return result;
}
} from collections import deque
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
# Base case
if not root:
return []
# Result list
result = []
# Deque for BFS
queue = deque([root])
# Flag to track if we need to reverse the level order list
reverse_flag = False
# Loop while queue is not empty
while queue:
# Get the size of the queue
size = len(queue)
# Temporary list to store the nodes at the current level
curr_level = []
# Loop through the queue
for _ in range(size):
# Pop the first node from the queue
node = queue.popleft()
# Append the node to the current level list
curr_level.append(node.val)
# Add the left child to the queue
if node.left:
queue.append(node.left)
# Add the right child to the queue
if node.right:
queue.append(node.right)
# Append the current level list to the result
if reverse_flag:
result.append(curr_level[::-1])
else:
result.append(curr_level)
# Toggle the reverse flag
reverse_flag = not reverse_flag
# Return the result
return resultvar zigzagLevelOrder = function(root) {
//zigzagLevelOrder is a function that takes in a root node of a tree and outputs
//an array of arrays where each subarray is the values of the nodes at each level
//of the tree in zigzag order
//if the root is null, return an empty array
if(!root) {
return [];
}
//create an array to store the final output
let output = [];
//create a queue to store the nodes at each level
let queue = [root];
//create a variable to keep track of the current level
let level = 0;
//while the queue is not empty
while(queue.length > 0) {
//create an array to store the nodes at the current level
let currentLevel = [];
//get the number of nodes at the current level
let levelSize = queue.length;
//for each node at the current level
for(let i = 0; i < levelSize; i++) {
//get the node from the queue
let node = queue.shift();
//if the level is even
if(level % 2 === 0) {
//add the node to the currentLevel array
currentLevel.push(node.val);
} else {
//add the node to the beginning of the currentLevel array
currentLevel.unshift(node.val);
}
//if the node has a left child, add it to the queue
if(node.left) {
queue.push(node.left);
}
//if the node has a right child, add it to the queue
if(node.right) {
queue.push(node.right);
}
}
//add the currentLevel array to the output array
output.push(currentLevel);
//increment the level
level++;
}
//return the output array
return output;
};/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector> zigzagLevelOrder(TreeNode* root) {
vector> result;
if (!root) return result;
queue q;
q.push(root);
int level = 0;
while (!q.empty()) {
int size = q.size();
vector currLevel;
for (int i = 0; i < size; i++) {
TreeNode* curr = q.front();
q.pop();
if (level % 2 == 0) {
currLevel.push_back(curr->val);
} else {
currLevel.insert(currLevel.begin(), curr->val);
}
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
result.push_back(currLevel);
level++;
}
return result;
}
}; /**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
public IList> ZigzagLevelOrder(TreeNode root) {
//result list
IList> result = new List>();
//edge case
if(root == null)
{
return result;
}
//queue for bfs
Queue queue = new Queue();
//add root to queue
queue.Enqueue(root);
//level counter
int level = 0;
//while queue is not empty
while(queue.Count != 0)
{
//list for current level
IList currentLevel = new List();
//number of nodes in current level
int level_length = queue.Count;
//for each node in current level
for(int i = 0; i < level_length; i++)
{
//get node from queue
TreeNode node = queue.Dequeue();
//if level is even, add node value to the end of currentLevel list
if(level % 2 == 0)
{
currentLevel.Add(node.val);
}
//if level is odd, add node value to the beginning of currentLevel list
else
{
currentLevel.Insert(0, node.val);
}
//if node has left child, add to queue
if(node.left != null)
{
queue.Enqueue(node.left);
}
//if node has right child, add to queue
if(node.right != null)
{
queue.Enqueue(node.right);
}
}
//add currentLevel list to result
result.Add(currentLevel);
//increment level counter
level++;
}
return result;
}
}