Given a binary Tree, write a code to return binary tree zigzag level order traversal of its node’s values. (ie, from left to right, then right to left for the next level and alternate between).
In the screenshot below, We have printed the zigzag traversal of a binary tree. We have printed the values from left to right for the first level. For the second level, we then moved from right to left. Then for the next level, we move from left to right and so on.
Binary Tree Spiral Traversal
Now we have discussed the problem statement. The next thing is let’s think about how we can solve this problem efficiently.
In this tutorial, I am going to discuss how we can solve this problem using level order traversal. Also, at the end of this tutorial, I have shared the link to the video tutorial.
Binary Tree Zigzag Level Order Traversal using Queue – Java Code
We can solve this problem using the level order traversal of a binary tree. While doing the level order traversal, we also need to declare one variable which helps us to identify the direction of visit.
To do the zigzag traversal of a binary tree, we have to visit all the nodes of the first level from left to right then the next level right to left, and so on. If we start the level number from 0, it means for all the even number levels we have to visit from left to right and for odd we have to visit right to left.
Here are the following steps to do zigzag traversal –
i) Declare a queue and add the root node in a queue. Also, add one variable level and initialize with 0.
ii) Run a while loop while the queue is not empty and do the following steps
a) poll a queue.
b) Enqueue left and right children of a node if it’s not null. c) If the value of level is even then add node values from left to right else add them from right to left.
d) Also, increment level after each iteration.
The time complexity of this approach is O(n) and it’s space complexity is also O(n).
Reverse level order traversal of a binary tree
Print right view of a binary tree
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
//Zigzag Level Order Traversal - Java Code public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> qu = new LinkedList<>(); qu.add(root); int level = 0; while (!qu.isEmpty()) { int len = qu.size(); List<Integer> levelResult = new ArrayList<>(); for (int i = 0; i < len; i++) { TreeNode temp = qu.poll(); //If left child is not null if (temp.left != null) qu.add(temp.left); //If right child is not null if (temp.right != null) qu.add(temp.right); if (level % 2 == 0) levelResult.add(temp.val); else levelResult.add(0, temp.val); } level++; result.add(levelResult); } return result; } |
Binary Tree Zigzag Level Order Traversal InterviewBit Solution
The similar problem is there in interview bit. Here are it’s java code.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
//InterviewBit Solution public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode A){ ArrayList<ArrayList<Integer>> result = new ArrayList<>(); if (A == null) return result; Queue<TreeNode> qu = new LinkedList<>(); qu.add(A); int level = 0; while (!qu.isEmpty()) { int len = qu.size(); ArrayList<Integer> levelResult = new ArrayList<>(); for (int i = 0; i < len; i++) { TreeNode temp = qu.poll(); //If left child is not null if (temp.left != null) qu.add(temp.left); //If right child is not null if (temp.right != null) qu.add(temp.right); if (level % 2 == 0) levelResult.add(temp.val); else levelResult.add(0, temp.val); } level++; result.add(levelResult); } return result; } |
