Hello friends!

And, welcome to another tutorial on GeeksforGeeks. In this video we are going to understand the

program which converts a binary tree into Doubly Linked List in spiral fashion..First,

let us take an example.. As you can see, we have printed the elements

of this tree in a spiral fashion.. Now, let us see the algorithm.. Let us also have a sample tree to test our

algorithm We pass the root node to function spiralLevelOrder..

So, root will point to 1 and we push 1 into a dequeue. Also, we create a stack to store binary tree

nodes We take a level variable an initialize it

to zero, Now, as the queue is not empty we enter the

while loop and take another variable nodeCount which stores the nuber of nodes

at current level. Now we check if level is odd or even.. Since

level is zero, we take it as even level and go to the else part.. Now, as nodeCount

is greater than zero, we enter the while loop in the else part.. Next, we dequeue

node from back of the queue and push it into the stack. So, node will point

to 1.. And 1 will be dequeued. Now we will push 1 into the stack. Now we will insert node’s right and left

children in the queue.. So, first we insert right child of 1 at front of the queue. And now we insert the left child of 1 in the

front of the queue. Next, we decrement nodeCount. So, it will

be now zero As nodeCount is not greater than zero, we

come out of the inner while loop and increment level.. We continue with the outer while loop as the

queue is not empty.. Now, nodeCount will be equal to 2 as there are

2 elements in the queeu. Now as it is an odd level, the first if condition

gets satisfied and now as nodeCount is greater than zero, we dequeue node from

front and push it in stack.. So, node will point to 2.. 2 will be dequeued. Next, we push 2 into the stack. Now we will insert its left and right children

at back of the dequeue. So,4 and 5 will be enqueud. Next, we decrement nodeCount. As nodeCount is greater than zero, we continue

with the inner while loop and pop the node from the front.. SO, node will point

to 3 and 3 will be popped. Next, we push 3 into the stack. Now we insert the left and right children

of 3 into the queue. So, 6 and 7 will be enqueued in the dequeue. We decrement nodeCount This time nodeCount is not greater than zero,

so we come out of the inner while loop and increment level. As the queue is not empty, nodeCount will

be equal to 4 as there are 4 elements in the qeueu. As 2 is an even level, we go to the else part..

Now as nodeCount is greater than zero, we dequeue a node from the back of the

queue. SO, node will point to 7 and 7 will be dequeued. Now, we push 7 into the stack. As 7 does not have left and right children,

we decrement nodeCount. Since nodeCount is>0 we continue with

the while loop and now node will point to 6 and 6 will be dequeued and pushed into the

stack. As 6 does not have any children, we decrement

nodeCOunt. NodeCount is greater than zero so we continue

with the while loop.. Now, node will point to 5 and 5 will be dequeud and

pushed into the stack. NodeCount is greater than zero so we continue

with the while loop.. Now, node will point to 5 and 5 will be dequeud and

pushed into the stack. Since nodeCount is greater than zero, we dequeue

4 from the queue and push it into the stack.. Since nodeCount is greater than zero, we dequeue

4 from the queue and push it into the stack.. As nodeCount is not greater than zero, we

come out of the inner while loop and now as the queue is empty, we come out of

the outer while loop as well.. We take a headpointer and point it to NULL. NOw, we will pop all the node sfrom the stack

one by one and push them in the beginning of the list.Note that we are assuming

that the function for creation of DLL is already there and we are passing elements

for the list…So, after popping each element one by one, we will have the

final DLL. Now let us have a look at the time complexity

of the program. This code will run in O(n) complexity.Here

n are the number of nodes in our binary tree.

With this we come to an end of this tutorial. For any doubts or suggestions please leave

them in the comment section below. Thanks for watching!