Yesterday, while browsing on internet I landed up on a good, yet very basic DS and algorithm problem. Its not that difficult to solve, but can go a little weird if you miss out or go wrong at 1 or 2 pointer changes. ok, so here goes the problem:

Given a Binary search Tree ( I assume here, that most of you are aware of it, by now at least. Others, may like to read

this before reading this problem further). You have to create a recursive function, which takes a BST and returns the corresponding Circular Doubly linked list.

Ok. Lets consider a sample BST (Binary Search Tree)

a(5)

/ \

b(3) c(6)

/ \ \

d(2) e(4) f(7)

[Note: the letters 'a','b'... are the names given to the nodes and the value in the parenthesis indicates the numeric data of that node]

Now our objective is to make a recursive function which takes the above tree as input and returns a circular doubly linked list, somewhat like this:-

d(2)==b(3)==e(4)==a(5)==c(6)==f(7)==d(2) ( its circular)

here the 'left' and 'right' pointers of the Node of the BST, will be treated analogous to 'previous' and 'next' in the linked list.

A little thought to the problem, and I came up with following solution. Heres the intended function's pseudo code:-

function bstToList(root)

{

//for leaf node return itself ( case 1)

if (root.left == root and root.right == root)

return root

//no left subtree exist (case 2)

else if (root.left == root)

{

head2 = bstToList(root.right) //call recursively

root.right = head2

head2.left.right = root //head2.left refers to the last node in the list

root.left = head2.left

head2.left = root

return root

}

//no right subtree exist (case 3)

else if (root.right == root)

{

head1 = bstToList(root.left) //call recursively

root.left = head1.left //head1.left refers to the last node in the list

head1.left.right = root

root.right = head1

head1.left = root

return head1

}

//both left and right subtrees exist (case 4)

else

{

h1 = bstToList(root.left) //call recursively and find the head nodes of both sublists

h2 = bstToList(root.right)

l1 = h1.left //find last nodes of the sublists

l2 = h2.left

h1.left = l2 //join the ends of both sublists

l2.right = h1

l1.right = root //insert the root to the end of left sublist

root.left = l1

root.right = h2 //insert the right sublist to the right of root

h2.left = root

return h1 //return the head node

}

} //function ends

As evident, the function considers 4 major cases:-

1. When the current node(root) is a leaf node( a leaf node is one with no children)

2. When there exists no left subtree/child

3. When there exists no right subtree/child

4. When there exists both left and right subtree/child

In every call the function tries to append the current node to the already formed doubly linked lists at the appropriate position.( it can be easily figured out in the above code in case 4)

Here goes the complete implementation(its in Python, but can be understood, inspite of my terrible coding style):-

class node:

''' class to represent a node of BST/ linked list'''

def __init__(self, data):

self.data = data

self.left = self

self.right = self

def printBST(root):

'''prints the BST in an inorder sequence'''

if root.left == root or root.right == root:

print root.data, " ",

else:

printBST(root.left)

print root.data, " ",

printBST(root.right)

def printList(head):

'''prints the linked list in both directions

to test whether both the 'next' and 'previous' pointers are fine'''

#print forward direction

h = head

print '[%d]' % (h.data),

h = h.right

while h != head:

print '[%d]' % (h.data),

h = h.right

print ""

#print in reverse direction

h = head.left

print '[%d]' % (h.data),

h = h.left

while h != head.left:

print '[%d]' % (h.data),

h = h.left

def bstToList(root):

'''

main function to take the root of the BST and return the head of the

doubly linked list

'''

#for leaf node return itself

if root.left == root and root.right == root:

return root

elif root.left == root: #no left subtree exist

h2 = bstToList(root.right)

root.right = h2

h2.left.right = root

root.left = h2.left

h2.left = root

return root

elif root.right == root: #no right subtree exist

h1 = bstToList(root.left)

root.left = h1.left

h1.left.right = root

root.right = h1

h1.left = root

return h1

else: #both left and right subtrees exist

h1 = bstToList(root.left)

h2 = bstToList(root.right)

l1 = h1.left #find last nodes of the lists

l2 = h2.left

h1.left = l2

l2.right = h1

l1.right = root

root.left = l1

root.right = h2

h2.left = root

return h1

if __name__ == "__main__":

#create the sample BST

root = a = node(5)

b = node(3)

c = node(6)

d = node(2)

e = node(4)

f = node(7)

a.left, a.right = b, c

b.left, b.right = d, e

c.right = f

printBST(root)

print "\ncreating to double linked list"

head = bstToList(root);

printList(head)

I am sure this is not the best way to go, but it surely solve the problem in a recursive way. Comments welcome

Happy Coding! :~) @_@