Earth Hour

Wednesday, April 7, 2010

Finding the 'First Common Ancestor' in a Binary Tree

Just this morning, I received a basic question related to Binary Trees(not necessarily Binary 'Search' Trees) from a fellow at an algorithm forum. So here I am posting my solution to it.
The problem goes like this(pretty simple 1 line problem):- Given a Binary Tree (not necessarily Binary 'Search' Tree), its root and pointers to any 2 nodes of the tree, find out the first common ancestor of the Tree. A Node of the tree contains: data, left subtree pointer, right subtree pointer but no 'Parent pointer'.

Logic: Let 'A' and 'B' be the given too node whose common ancestor we have to find. Now perform an inorder traversal of the tree and at every node call the 'search(A)' function on the left subtree and search(B) function on the right subtree. When both the results are true, you can be assured that this current node is only the first common ancestor of A, and B,
Reason: Let the first common ancestor node be 'C'. Then below C on either of its subtree tree (left and right) one and only one of the nodes amongst A and B will be present and above the hierarchy of node C, both A and B will exist on just the 1 side.
Heres d pseudo code:

function getFirstCommonAncestor(root, A, B):
if root == NULL:
return NULL // the tree doesnt exists

// if the left subtree contains node A and the right subtree contains node B then we have found the first common ancestor
if(searchTree(root.left, A) and searchTree(root.right, B)):
return root

//else recursively find the common ancestor on its left and right subtrees and return if found
L = getFirstCommonAncestor(root.left, A, B)
R = getFirstCommonAncestor(root.right, A, B)

if L != None:
return L
if R != None:
return R

return None

Well, the algorithm is not so efficient but solves our purpose partially. I am yet to further include additional conditional checks and optimize the algorithm, but for most of the cases it works just fine. :)

Here goes the complete implementation in Python.

Note: Some of the extra checks are missing. You will figure that out yourself.

Bye for now.
Happy Coding !

Wednesday, March 31, 2010

Converting a BST to circular Doubly linked list

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)

/ \
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)
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): = 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, " ",
print, " ",

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 = h.right
while h != head:
print '[%d]' % (,
h = h.right

print ""
#print in reverse direction
h = head.left
print '[%d]' % (,
h = h.left
while h != head.left:
print '[%d]' % (,
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


print "\ncreating to double linked list"
head = bstToList(root);


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

Wednesday, March 24, 2010


For many of my friends who are not able to connect to IRC due to blocking of its ports, here is the application, which works on HTTP, you can join the desired Rooms and chat:-

(thanks to:

Monday, March 22, 2010

Tablet War Begins

After the launching of a yet another success product from Microsoft, i.e. Windows 7, after Windows XP, which was one of the most successful of the MS products. MS came up with several new innovations in its new OS, including the "Multi Touch interface", although the concept was existing even before the launch of Win7, but it still was lacking a completeness, fully support and a tight integration with an OS. It literally warmed up the technical market. As you all might be aware of, now Ubuntu also comes with support for multi touch screen display. But with the onset of the OS' supporting multi-touch displays, the market seems to be hit by many Tablet PC products, like Apples hits the market by its new I-PAD, soon the race was caught up by NotionInks ADAM, and JKKs Hanvon to make things 'not so simple' to Apple.
Here I have compiled a list (not exhaustive) of features for these products:-

Note that, there are many more to join ( and probably joined already) the crowed of Tablet PC production. But whatever it is, one thing is sure, there is no limit to innovation and there is always infinite scope for doing the new.

Useful links:

Disclaimer: The views expressed here are entirely my own and bear no intention to offend anyone. I am not against or for any company, organization or individual, but just express what I feel at the time of writing the post. Anyone is free to disagree with me and the ones who don't like my views are free not to read my blog ;)

Happy computing
Bye for now

Saturday, March 20, 2010

Ubuntu9.10 and Empathy

Alright, its been really a long time, since I posted anything to my blog. Many things happened in the meantime, and my computer was formatted a lot many times, and now I have an entirely different set of OSs. I installed Ubuntu 9.10, Karmic Koala, and to my surprise my beloved Pidgin IM Client was missing in it, which I was accustomed to. I tried to use Empathy but its been not even an hour and I downloaded Pidgin and installed it. But Somehow it seemed to be unstable on my IBM Thinkpad laptop. Unlike the previous times, it crashes frequently and soon I have to run away from it. I had no option but to explore the new Empathy. I soon was able to configure it to my taste. It not only has full support now for voice chat (unlike the previous times) but also comes in handy with the full and stable support for the desktop sharing with anyone over the internet, in just a click of the mouse!
Anyways, I know as soon as we install ubuntu or any other linux distro, where the beginners have to struggle a lot to initially hunt for a suitable client where they can talk to their google-talk contacts. So here are the google-talk settings which seem to work for me ( but I shall not be responsible if it doesnt turn out for you ). Ok, here it goes-
  1. Just Open your Empathy client ( I hope you know it, Applications-> Internet-> Empathy)
  2. Press F4 or Edit->Accounts and click Add button at the bottom of the left panel
  3. Select "Google Talk" as the account type and press "Create"
  4. Enter your login name along with the "" extension. Eg. if your login name is ABC then enter ""
  5. Enter your password, in the space provided
  6. Click Advance to expand the options and fill the following details:
    1. Select the option "Encryption required (TLS/SSL)"
    2. Select the option "Ignore Certificate Errors"
    3. Leave "Resource" and "Priority" blank ( default value)
    4. Enter the "Server" as ""
    5. Enter the "Port" as "443"
    6. Select the "Use old SSL" option
  7. Click "Apply" and you are done

Empathy offers a lot of features, most of them are pretty much similar to the Pidgin, like (what I can think as of now)-
  1. Configuring and Using multiple Chatting accounts like Gtalk, IRC, ICQ, Yahoo, MSN etc. simultaneously
  2. Support for file transfer feature ( although you need to check the file transfer server for the accounts over which the file is meant to be transferred)
  3. Audio Call
  4. Video Call
  5. "Share My Desktop" feature
  6. Join Different Chat rooms
  7. Few Themes also come bundled with the application
  8. Another feature which I liked more than Pidgin was the ease it offers to set the status message for all accounts at once (ya, its true, you have to sacrifice the facility of being able to set different status messages on different accounts)
Here is a screenshot of the application, for those who want to know how it looks :)
Happy Chatting !