Print binary tree in zigzag order | 103. Binary Tree Zigzag Level Order Traversal Leetcode
Write a program to print ZigZag order traversal of a binary tree. For the below binary tree the zigzag order traversal will be 1 3 2 4 5 6 7.
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).
Example 1:
Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]]
Example 2:
Input: root = [1] Output: [[1]]
Example 3:
Input: root = [] Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -100 <= Node.val <= 100
Solution:
- Let us take 2 Stack. One for the parent, second one for child
- boolean flag leftToRight for maintaining order in alternative fashion while adding right and left nodes.
- If the parent stack is empty
- Toggle the flag => leftToRight = !leftToRight;
- Assign child to parent stack => parent = child;
- Reset child stack => child = new Stack<>();
- Add current level to output => output.add(level);
- Reset Level => level = new ArrayList<>();
/*
Definition for a binary tree node.
*/
import java.util.*;
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<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> output = new ArrayList<>();
if(root == null)
return output;
Stack<TreeNode> parent = new Stack<>();
Stack<TreeNode> child = new Stack<>();
boolean leftToRight = true;
parent.add(root);
List<Integer> level = new ArrayList<>();
while(!parent.isEmpty()){
TreeNode node = parent.pop();
level.add(node.val);
if(leftToRight){
if(node.left!=null) child.add(node.left);
if(node.right!=null) child.add(node.right);
}
else{
if(node.right!=null) child.add(node.right);
if(node.left!=null) child.add(node.left);
}
if(parent.isEmpty()){
leftToRight = !leftToRight;
parent = child;
child = new Stack<>();
output.add(level);
level = new ArrayList<>();
}
}
return output;
}
public static void main(String args[]){
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
System.out.print(new Solution().zigzagLevelOrder(root));
}
}What is the time and space complexity of zigzag order traversal in binary tree?
Time Complexity: O(n)
Space Complexity: O(n)+(n)=O(n)
