cracking the coding interview in python – 4.6 common ancestor

Lets solve another exercise from the Trees and Graphs chapter and write some nice python code.
Here it is:

4.6 Design an algorithm and write code to find the first common ancestor of two nodes
in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not
necessarily a binary search tree.

Let’s write a test

First, lets create a tree and write a test. I don’t feel like creating a tree by hand so I’ll write a function to create a full binary tree for a given number of levels.
Let’s keep a simple representation of a tree:

class TreeNode:
    def  __init__(self, data, left=None, right=None):
        self.data=data
        self.left=left
        self.right=right

Now let’s write a function to create a tree. We need a unique name for each node, I’ll use a global variable for this purpuse.

def constructTree(levels, level=0):
    global total  
    if level==levels:
        return None
    total+=1
    newNode = TreeNode('node ' + `level`+"_"+`total`);
    newNode.left=constructTree(levels,level+1)
    newNode.right=constructTree(levels,level+1)
    return newNode

def get_node(head, name):
    "returns the first node with the given name"
    if not head:
        return None
    if (head.data==name):
        return head
    left = get_node(head.left, name)
    if left:
        return left
    return get_node(head.right, name)

For convenience, I also wrote a method to get a node by its name so I can easily write my tests.
Here they are:

 global total 
    total = 0
    t = constructTree(5)
    n1=get_node(t,'node 4_27')
    n2=get_node(t,'node 3_19')
    assert(firstAncestor(t,n1,n2).data=='node 1_17')
    n1=get_node(t,'node 2_18')
    n2=get_node(t,'node 4_16')
    assert(firstAncestor(t,n1,n2).data=='node 0_1')

The tree I build for the test looks like this:

'node 0_1'
    'node 1_2'
        'node 2_3'
            'node 3_4'
                'node 4_5'
                'node 4_6'
            'node 3_7'
                'node 4_8'
                'node 4_9'
        'node 2_10'
            'node 3_11'
                'node 4_12'
                'node 4_13'
            'node 3_14'
                'node 4_15'
                'node 4_16'
    'node 1_17'
        'node 2_18'
            'node 3_19'
                'node 4_20'
                'node 4_21'
            'node 3_22'
                'node 4_23'
                'node 4_24'
        'node 2_25'
            'node 3_26'
                'node 4_27'
                'node 4_28'
            'node 3_29'
                'node 4_30'
                'node 4_31'

First solution

The idea is to start from the head and traverse the graph level by level. At each step we will ask: is the current node the first common ancestor ?
It is if and only if the two nodes are located on left and right side of the current node. We will need a function to test if a node is contained in a given tree:

def containsNode(node,needle):
    if not node:
        return False
    if node==needle:
        return True
    return containsNode(node.left, needle) or containsNode(node.right, needle)

And now the function to find the first ancestor. Starting with the head, we use containsNode() function to test if the two nodes are located on left and right of the current node:

def firstAncestor(current, node1, node2):
    #special case: node1 first ancestor of node2 or viceversa
    if containsNode(node1, node2):
        return node1
    if containsNode(node2, node1):
        return node2    
    if not current:
        return None
    n1_left = containsNode(current.left, node1);
    n2_left = containsNode(current.left, node2);
    if (n1_left or n2_left) and not (n1_left and n2_left):
        return current
    if n1_left:
        return firstAncestor(current.left, node1,node2)
    else:
        return firstAncestor(current.right, node1, node2)

So what’s the complexity of this algorithm ? I would guess n*log(n) given the fact that I traverse the tree (with firstAncestor function) and, for each node, I traverse the tree having that node as head (with containsNode function). In my previous post we so this traversal was O(n*log(n))

Update

Well, I think I should pay more attention to the complexity.
Let’s count again the operations:
– firstAncestor() visits first node. It calls containsNode() twice for the left tree. Which gives us 2*n/2 operations. Then it goes to either left or right, dividing the remaining number of nodes by two, which gives us:

n + n/2 + n/4 + … operations = n (1 + 1/2 + 1//4 … ) which is upper bounded by 2n (see geometric serries ).
This gives us O(n)

Second and Best Solution

The idea is simple: for each of the two nodes we will find the path of nodes that leads from the head to the given node. Then we only need to put the 2 paths next to each other and see the common ancestor:

def path_to_node(current, needle, nodes=None):
    if nodes==None:
        nodes=[]
    
    if not current:
        return None
    buff=nodes[:]

    if current==needle:
        buff = [current]
        return buff

    left = path_to_node(current.left, needle, buff)
    if left:
        buff =  [current] + left
        return buff

    right = path_to_node(current.right, needle, buff)    
    if right:
        buff =  [current] + right
        return buff

def firstAncestorOptimized(head, node1, node2):
    l1 = path_to_node(head,node1)
    l2 = path_to_node(head,node2)
    k=0
    while l1[k]==l2[k]:
        k=k+1
    
    if k==0:
        return None
    return l1[k-1]

For me it looks like O(n).
That’s all for today.

Advertisements
This entry was posted in Cracking the coding interview - a python experience and tagged , , , . Bookmark the permalink.

One Response to cracking the coding interview in python – 4.6 common ancestor

  1. mebubo says:

    Some comments regarding python, not algorithms:

    1. You could do without the global variable using python’s limited support for closures:

    def constructTree(levels, level=0):
        total = [0]
        def loop(level):
            if level == levels:
                return None
            total[0] += 1
            newNode = TreeNode('node %s_%s' % (level, total));
            newNode.left = loop(level+1)
            newNode.right = loop(level+1)
            return newNode
        return loop(level)
    

    2. For XOR, you could write

    bool(n1_left) != bool(n2_left)
    

    3. A little bit nicer way to write your containsNode

    def contains(haystack, needle):
        return haystack and haystack == needle \
            or contains(haystack.left, needle) \
            or contains(haystack.right, needle)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s