Your task is to write a program to print the zigzag level-order traversal of a binary tree.
Here are a few examples :
1
/ \
2 3
Traversal : 1 3 2
1
/ \
2 3
/ \ \
4 5 6
Traversal : 1 3 2 4 5 6
1
/ \
2 3
/ \ \
4 5 6
/ / / \
7 8 9 10
Traversal : 1 3 2 4 5 6 10 9 8 7
Input
First line contains the number of nodes N.
Next N-1 lines contains information about one edge each.
Each line consists of three values : U V C which denotes that V is a child of U
If C is 'L' then V is a left child and if C is 'R' then V is a right child
Output
Print the zigzag level order traversal as explained
Sample Input 0
3
1 2 L
1 3 R
Sample Output 0
1 3 2import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
class Solution {
public static void main(String args[] ) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
String[] initChar = line.split(" ");
int N = Integer.parseInt(initChar[0]);
//int Q = Integer.parseInt(initChar[1]);
Map<Integer, Node> nodeMap = new HashMap<>();
for (int i = 0; i < N - 1; i++) {
String[] strArr = br.readLine().split(" ");
Integer parent = Integer.parseInt(strArr[0]);
Integer child = Integer.parseInt(strArr[1]);
if(strArr[2].equals("R")){
populateMapForRightNode(parent,child,nodeMap);
}else{
populateMapForLeftNode(parent,child,nodeMap);
}
}
Node root = nodeMap.get(1);
nodeMap=null;
printZigZagTraversal(root);
}
static void printZigZagTraversal(Node rootNode) {
// if null then return
if (rootNode == null) {
return;
}
// declare two stacks
Stack<Node> currentLevel = new Stack<>();
Stack<Node> nextLevel = new Stack<>();
// push the root
currentLevel.push(rootNode);
boolean leftToRight = true;
// check if stack is empty
while (!currentLevel.isEmpty()) {
// pop out of stack
Node node = currentLevel.pop();
// print the data in it
System.out.print(node.item + " ");
// store data according to current
// order.
if (leftToRight) {
if (node.left != null) {
nextLevel.push(node.left);
}
if (node.right != null) {
nextLevel.push(node.right);
}
}
else {
if (node.right != null) {
nextLevel.push(node.right);
}
if (node.left != null) {
nextLevel.push(node.left);
}
}
if (currentLevel.isEmpty()) {
leftToRight = !leftToRight;
Stack<Node> temp = currentLevel;
currentLevel = nextLevel;
nextLevel = temp;
}
}
}
private static void populateMapForRightNode(Integer parent,Integer child,Map<Integer, Node> nodeMap){
if(nodeMap.get(parent)==null){
Node node = new Node(parent);
node.right = new Node(child);
nodeMap.put(parent,node);
nodeMap.put(child,node.right);
}else{
Node node = nodeMap.get(parent);
node.right = new Node(child);
nodeMap.put(child,node.right);
}
}
private static void populateMapForLeftNode(Integer parent,Integer child,Map<Integer, Node> nodeMap){
if(nodeMap.get(parent)==null){
Node node = new Node(parent);
node.left = new Node(child);
nodeMap.put(parent,node);
nodeMap.put(child,node.left);
}else{
Node node = nodeMap.get(parent);
node.left = new Node(child);
nodeMap.put(child,node.left);
}
}
private static class Node{
public int item;
public Node left;
public Node right;
public Node(int item){
this.item = item;
}
}
}
