Question
|
Difficulty Level:
4
|
Solution
|
Explanation Quality:5
|
Most of you have studied trees in an algorithm class where it is often mentioned
that trees are naturally recursive data structures and are best dealt using recursive
algorithms. Whenever you embark on designing a recursive algorithm, it is important
that you mention to your interviewer that recursive algorithms are generally slower
and less efficient on account of the multiple recursive function calls
that they make but are easier to code and design. This is in contrast to corresponding
iterative algorithms which are though more efficient and faster but relatively compex
in design and code.
Note that if we take away the sorted requirement for the time being then we can
simply use a breadth first or depth first tree traversal algorithm and add each
node that we visit in our traversal to the doubly linked list. Once we are done
making our doubly linked list we can then sort our list using the best sorting algorithm.
Let's see the time complexity for this naive solution. Assume there are n nodes
in the tree. Using depth first search algorithm would take us nlogn time to traverse
the tree. The resulting doubly linked list will have n items in it and sorting it
using merge sort would take nlogn time. Total time would be 2nlogn. In big O notation
we can drop the constant 2 and say our time would be O(nlogn)
However we would next try to convert this two step algorithm into a single step
one. We would take help from the way a balanced binary tree is structured. Note
that in a binary tree the parent is greater than the left child but less than the
right child, assuming there are no duplicates within the tree. This information
lends us a tip in designing our algorithm.
If we are able to visit the left child first, then the parent and finally the right
child we would visit the nodes of the tree in order. Such a traversal of a tree
is called an in-order traversal. FYI, there is also the post-order and pre-order
traversals of the tree. The post order traversal visits the parents after visiting
the two children and the pre-order traversal visits the parents before visiting
it's two children.
All we do now is write code for in-order traversal and then adjust parent to child
pointers in the tree appropriately for the visited nodes so that the resulting structure
is a sorted doubly linked list. First let me show you the code for an in-order traversal
of the tree.
void inOrderTraversal(node* ptr){
if(ptr->leftChild){
inOrderTraversal(ptr->leftChild);
}
fprintf(stdout,"Print Parent Node Here");
if(ptr-rightChild){
inOrderTraversal(ptr-rightChild);
}
}
Now we know that we are visiting the nodes in the nodes in the tree in-order and
all we have to make sure now is to change the pointer connections correctly now.
Now that we are visiting the nodes in a sorted order we just need to stitch them
in a doubly linked list as each one comes through. In order to understand how we
can do that consider the given tree. Take the node numbered 2. It has a left child
1 and a right child 3. If I stitch 1 before 2 and 3 after 2, I will have the subtree
rooted at 2 in the form of a sorted linked list. Now I can pass this sorted linked
list up to the root of the tree which is 4 and the end of this sorted linked list
can be attached to 4 thus giving us 1, 2, 3 and 4 in a sorted doubly linked list.
If I apply the same pattern in the right branch of the original tree, then the root
4 would receive a sorted linked list from the left branch and a sorted linked list
from the right branch. All that needs to be done is that 4 attaches itself at the
end of the list receivedfrom the left branch and just before the start of the list
received from the right branch.
So now the recursive pattern becomes clear. At the leaves of the tree we just send
the node back up since it is a single element doubly linked list with the start
and the end pointing to itself. And for nodes within the tree(which aren't leaf
nodes) we send sorted linked lists up, to which the receiving node correctly attaches
in order to get a finally sorted doubly linked list. Note that we are thinking in
terms of creating linked lists recursively until we get the completely sorted lists
containing all the nodes of the original tree. Here is the entire algorithm.
void collapseIntoSortedList(node* ptr, start, end){
/*This is the base case*/
if(!ptr->leftChild && !ptr->rightChild){
start = end = ptr;
return;
}
if(ptr->leftChild){
pointer *tempStart, *tempEnd;
collapseIntoSortedList(ptr->leftChild, tempStart, tempEnd);
}
ptr->prev = tempEnd;
tempEnd->next = ptr;
start = tempStart;
if(ptr-rightChild){
collapseIntoSortedList(ptr-rightChild, tempStart, tempEnd);
}
ptr->next = tempStart;
tempStart->prev = ptr;
end = tempEnd;
}
Note the variables tempEnd and tempStart. Both these variables
are used to record the start and end of the partially sorted doubly linked list
that we'll be passing to the upper level of the tree. Also take caution that this
might NOT be the optimal recursive algorithm but it is good enough for an interview.
|