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()