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!