PROBLEM DESCRIPTION
Given a binary tree and the task is to find the spiral order traversal of the tree.
Spiral order Traversal mean: Starting from level 0 for root node, for all the even levels we print the node’s value from right to left and for all the odd levels we print the node’s value from left to right.
SOLUTION
We can use level order traversal. We can maintain the current level in a variable, incremented with 1 after each iteration. When the level is even, we can reverse the node list.
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
class Spiral
{
ArrayList<Integer> findSpiral(Node root)
{
// queue for level order traversal
Queue<Node> q = new LinkedList<>();
// add root to the queue
q.add(root);
// result
ArrayList<Integer> list = new ArrayList<>();
// track current level
int level = 0;
// while queue is not empty
while(!q.isEmpty()){
// get num of nodes in the current level
int size = q.size();
// nodes in the current level
ArrayList<Integer> currentLevel = new ArrayList<>();
// add them one by one to the current level list
// add their left and right to the queue to visit them for the next level
for(int i=0; i<size; i++){
Node currentNode = q.poll();
currentLevel.add(currentNode.data);
if(currentNode.left != null)
q.add(currentNode.left);
if(currentNode.right != null)
q.add(currentNode.right);
}
// even levels we print the node's value from right to left
if(level%2 == 0)
Collections.reverse(currentLevel);
// add the current level to the overall result
list.addAll(currentLevel);
// increase level for the next iteration
level++;
}
return list;
}
}