How to convert a binary search tree into a doubly linked list?

Question

Given a binary search tree, i need to convert it into a doubly linked list(by traversing in zig zag order) using only pointers to structures in C++ as follows,

Given Tree:

                1
                |
        +-------+---------+
        |                 |
        2                 3
        |                 |
   +----+---+        +----+---+
   |        |        |        |
   4        5        6        7
   |        |        |        |
+--+--+  +--+--+  +--+--+  +--+--+
|     |  |     |  |     |  |     |
8     9  10    11 12    13 14    15

Node Structure:

struct node
{
    char * data;
    node * left;
    node * right;
};

Create List(zig zag order):

1 <-> 3 <-> 2 <-> 4 <-> 5 <-> 6 <-> 7 <-> 15 <-> ... <-> 8

Could someone please help me out.

Answer 1

you can write a function to add nodes in a doubly linked list. You can then call this function while traversing the tree. In this way you should be able to do it.

Answer 2

That's an awkward type of tree traversal. I wonder how often anyone has ever actually needed to do such a thing in real code. Nevertheless, it's the problem to be solved here...

Here's how I would approach dealing with this:

First, when I compare the desired output to the structure of the tree, I notice that each "level" of the tree is processed in turn from top to bottom. So top node first, then all child nodes, then all grand-child notes, and so on. So probably a good solution will involve a loop that processes one level and at the same time builds up a list of nodes in the next level to be used in the next iteration of the loop.

Next, this "zig zag" order means it needs to alternate which direction the child nodes are processed in. If a particular iteration goes from left to right, then the next iteration must go from right to left. And then back to left to right for the subsequent iteration and so on. So in my idea of a loop that processes one level and builds a list of the next level, it probably needs to have some sort of alternating behavior when it builds that list of nodes for the next level. On even iterations the list is built one way. On odd iterations the list is built the other way.

Alternatively, another other way to think about this whole thing is: Design a solution to that can build the result list in 1,2,3,4,5,6,etc order. Then modify that design to have the zig zag order.

Does this give you enough of an idea on how to design a solution?

Answer 3

Hmm... This is a tough one. The problem with traversal in this order is that you are doing a lot of skipping around. This is generally true in any tree traversal order that is not depth or breadth first.

Here's how I would resolve the situation. Start with a single, empty array of lists of nodes and begin traversing the tree depth first. Be sure to keep track of the depth of your traversal.

At each point in traversal, note the depth of your traversal and pick the list at the index in the array. If there isn't one there, add it first. If the depth is even (Assuming root has depth 0), add the node to the end of the list. If it's odd, add it to the beginning.

Once you've traversed all nodes, concatenate the lists.

Answer 4

This is a Breadth-first search algorithm. Wikipedia has a good explanation on how to implement it.

After implementing the algorithm, creating your linked list should be a no-brainer (since it will only be a matter of appending each visited element to the list)

Answer 5

This might help you:

1. Create a separate list for every level of the tree
2. Traverse the tree and copy the values to the lists as you traverse the tree
3. Reverse the order of every other list
4. Connect the lists

Answer 6

Why use pointers?? You could just store your BST as an array A[1...n]. So, A[1] would have root, A[2] and A[3] would have nodes of the depth 1, etc. This is possible since it is an almost complete tree, and you know how many elements will be present at a given depth - i.e. 2^d at depth d (except of course at the last depth). Now all you've got to do is access the array in a zag-zag manner, and create a new BST (array) of the new order. So, how would you traverse the array in a zig-zag manner?? For any given element A[i], the left child would be A[2i] and the right child A[2i + 1]. So, if your current depth d is odd, then traverse 2^d elements, and when you reach the 2^dth element, go to its left child. If your current depth d is even, again traverse 2^d elements, but when you reach the 2^dth element, go to its right child. Storing them as arrays rather than nodes makes your data structure leaner, and your implementation simpler.

Answer 7

This ( http://cslibrary.stanford.edu/109/TreeListRecursion.html) has the answer with pretty pictures :)