Binary Search Tree – Lowest Common Ancestor – Python

The last problem in the Trees chapter of Programming Interviews Exposed was about finding the lowest common ancestor between two nodes of a binary search tree. Starting from the head, if you find that the nodes that you’re looking for straddle the node you’re on, then you’ve found your lowest common ancestor. If they’re both on one side or the other, grab your child on that side, and recurse. The key is realizing that when you go left (for example) there will be no result on the left branch bigger than the right’s universe.

def commonAncestor(node1,node2,head):
    """ 
    >>> node1=Node(1)
    >>> node4=Node(4)
    >>> node3=Node(3,node1,node4)
    >>> node7=Node(7)
    >>> node5=Node(5,node3,node7)
    >>> commonAncestor(node1,node7,node5).value
    5
    >>> commonAncestor(node7,node1,node5).value
    5
    >>> commonAncestor(node1,node5,node5).value
    5
    >>> commonAncestor(node1,node4,node5).value
    3
    >>> commonAncestor(node7,node7,node5).value
    7
    """
    maxNode=max([node1,node2], key=lambda item: item.value)
    minNode=min([node1,node2], key=lambda item: item.value)
    if head==None: return
    if (minNode.value <= head.value) & (maxNode.value >= head.value):
        return head
    if (minNode.value <= head.value) & (maxNode.value <= head.value): 
        return commonAncestor(node1,node2,head.left) 
    if (minNode.value >= head.value) & (maxNode.value >=head.value):
        return commonAncestor(minNode,maxNode,head.right)

class Node:
    def __init__(self,value,left=None,right=None):
        self.value=value
        self.left=left
        self.right=right

import doctest                                                                                                                                                                                                  
doctest.testmod()
This entry was posted in programming and tagged , , , . Bookmark the permalink.

2 Responses to Binary Search Tree – Lowest Common Ancestor – Python

  1. pracha says:

    why r u assumin it to be bst

  2. Anonymous says:

    What if:
    node1.value>=head.value & node2.value<=head.value

    Your code doesn't cover that case.

Leave a Reply

Your email address will not be published. Required fields are marked *