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)