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<>();
• 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;

List<Integer> level = new ArrayList<>();
while(!parent.isEmpty()){
TreeNode node = parent.pop();
if(leftToRight){
}
else{
}
if(parent.isEmpty()){
leftToRight = !leftToRight;
parent = child;
child = new Stack<>();
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)