Rebrained!

BinaryTree – 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 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(node1,node5,node5).value
    5
    commonAncestor(node1,node4,node5).value
    3
    """
    if head==None: return
    if (node1.value<=head.value)&(node2.value>=head.value):
            return head
    if (node1.value<=head.value)&(node2.value<=head.value):
            return commonAncestor(node1,node2,head.left)
    if (node1.value>=head.value)&(node2.value>=head.value):
            return commonAncestor(node1,node2,head.right)

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

if __name__ == "__main__":
    import doctest
    doctest.testmod()