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! :~) @_@
Posts
