-
Notifications
You must be signed in to change notification settings - Fork 25
/
ZigZag_Tree_Traversal.java
140 lines (111 loc) · 3.02 KB
/
ZigZag_Tree_Traversal.java
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
import java.util.*;
import java.util.HashMap;
import java.io.*;
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
left = null;
right = null;
}
}
public class GFG2 {
static Node buildTree(String str) {
if (str.length() == 0 || str.charAt(0) == 'N') {
return null;
}
String ip[] = str.split(" ");
// Create the root of the tree
Node root = new Node(Integer.parseInt(ip[0]));
// Push the root to the queue
Queue<Node> queue = new LinkedList<>();
queue.add(root);
// Starting from the second element
int i = 1;
while (queue.size() > 0 && i < ip.length) {
// Get and remove the front of the queue
Node currNode = queue.peek();
queue.remove();
// Get the current node's value from the string
String currVal = ip[i];
// If the left child is not null
if (!currVal.equals("N")) {
// Create the left child for the current node
currNode.left = new Node(Integer.parseInt(currVal));
// Push it to the queue
queue.add(currNode.left);
}
// For the right child
i++;
if (i >= ip.length)
break;
currVal = ip[i];
// If the right child is not null
if (!currVal.equals("N")) {
// Create the right child for the current node
currNode.right = new Node(Integer.parseInt(currVal));
// Push it to the queue
queue.add(currNode.right);
}
i++;
}
return root;
}
public static void inorder(Node root) {
if (root == null)
return;
inorder(root.left);
System.out.print(root.data);
inorder(root.right);
}
/* Drier program to test above functions */
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while (t > 0) {
String s = br.readLine();
Node root = buildTree(s);
GFG g = new GFG();
ArrayList<Integer> res = g.zigZagTraversal(root);
for (int i = 0; i < res.size(); i++)
System.out.print(res.get(i) + " ");
System.out.println();
t--;
}
}
}
class GFG {
ArrayList<Integer> zigZagTraversal(Node root) {
ArrayList<Integer> ans = new ArrayList<>();
if (root == null)
return ans;
Stack<Node> st1 = new Stack<>();
Stack<Node> st2 = new Stack<>();
Boolean leftToRight = true;
st1.push(root);
while (!st1.isEmpty()) {
Node curr = st1.pop();
ans.add(curr.data);
if (leftToRight) {
if (curr.left != null)
st2.push(curr.left);
if (curr.right != null)
st2.push(curr.right);
} else {
if (curr.right != null)
st2.push(curr.right);
if (curr.left != null)
st2.push(curr.left);
}
if (st1.isEmpty()) {
leftToRight = !leftToRight;
Stack<Node> temp = new Stack<>();
temp = st1;
st1 = st2;
st2 = temp;
}
}
return ans;
}
}