For example
4
/ \
3 7
/ \ / \
8 2 9 6
/ \
1 5
(Input Binary Tree)
To
4 - 7 - 3 - 8 - 2 - 9 - 6 - 5 - 1 - NULL
or
4 - 3 - 7 - 6 - 9 - 2 - 8 - 1 - 5 - NULL
This question was posted on Career cup.
This was the solution that I had posted there. I was not able to format the comment properly there so I am doing it here. This solution uses forward direction to represent forward and backward link in the doubly linked list.
Using 1 stack, 2 variables and 2 pointers.
Key to this solution is to remember 2 things, there are 2 phase and 2 directions
Direction
1)Forward - take left child first and then right child
2)Backward - the reverse of forward.
Phases
1) Seeding phase - push to stack
2) Growing phase - get from the stack and add it to the list
Seeding phase
new nodes in the linked list will one by one start pushing their children in the stack. If the current direction is forward then left will be pushed first and the right will be pushed first in the case of backward. If the child is NULL nothing is done.
Example 1: let there be only 4 in the current list (4 -> null) and dir be forward, then 4 will start seeding in the forward direction. So after the seeding phase we will have
Seeding Phase, direction: forward
4
/ \
3 7
/ \ / \
8 2 9 6
/ \
1 5
(Input Binary Tree)
4 will push 3 then 7
| 7 |
4 -> null | 3 |
-----
(List) (Stack)
Growing phase
From the stack each node is poped and added to the linked list. After the end of the growing phase these nodes will seed.
Example 2 (continuing from the prev ex): After the growing phase we will have
V | |
4 -> 7 -> 3 -> null | |
^ ----
(List) (Stack)
V - shows where the seeders will start
^ - shows where the tail node is
Algorithm
To convert the binary tree to Zig-zag traversed Linked list we do the following
If ( stack empty and V is pointing to NULL)
THE END
If (the stack is empty)
reverse direction
start seeding
If (V is pointing to NULL)
start growing.
If V is pointing to NULL we will point V to the next element poped..
Update tail when a new element is added to the list.
-----------------------------------------------------------
Example 3: Continuing from the previous example, we have the following
4
/ \
3 7
/ \ / \
8 2 9 6
/ \
1 5
(Input Binary Tree)
V | |
4 -> 7 -> 3 -> NULL | |
^ ----
(List) (Stack)
Direction: Forward
The stack is empty, so we reverse the direction and start seeding backwards (i.e. Push right child first into the stack then left child)
The stack is empty so
Reverse the direction
Start seeding.
3 will push 2 then 8
Which gives us
| 8 |
V | 2 |
4 -> 7 -> 3 -> NULL | 9 |
^ | 6 |
----
There are no more node to spawn children. So we start popping nodes from the stack and add them to the list. We also set V to the first element popped to mark the node from which seeding will start in the next phase.
V is pointing to null so
Start growing
Point V to the first node poped
This will give us
V | |
4 -> 7 -> 3 -> 8 -> 2 -> 9 -> 6 -> NULL | |
^ ----
(List) (Stack)
Continuing with the same logic. Seeding forward (i.e. Pushing left child first then right child)
8 will push 1
2 has nothing push
9 will push 5
6 has nothing push
so we have
V | 5 |
4 -> 7 -> 3 -> 8 -> 2 -> 9 -> 6 -> NULL | 1 |
^ ----
(List) (Stack)
Growing...
V | |
4 -> 7 -> 3 -> 8 -> 2 -> 9 -> 6 -> 5 -> 1 -> NULL | |
^ ----
Seeding backwards...
1 has nothing push
V | |
4 -> 7 -> 3 -> 8 -> 2 -> 9 -> 6 -> 5 -> 1 -> NULL | |
^ ----
Stack empty and V is pointing to NULL
THE END
4 -> 7 -> 3 -> 8 -> 2 -> 9 -> 6 -> 5 -> 1 -> NULL
We started root with forward direction so we came up with this order had we started with root in reverse direction we should end up with
4 -> 3 -> 7 -> 6 -> 9 -> 2 -> 8 -> 1 -> 5 -> NULL
To create forward and backward links we can fix left pointer as forward and right pointer as backward. Space and time complexity of the algorithm is O(n).
