Posts Level order traversal in spiral form (geeksforgeeks - SDE Sheet)
Post
Cancel

Level order traversal in spiral form (geeksforgeeks - SDE Sheet)

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.

geeksforgeeks

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;

    }

}
This post is licensed under CC BY 4.0 by the author.