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()
- 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()
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()
why r u assumin it to be bst
What if:
node1.value>=head.value & node2.value<=head.value
Your code doesn't cover that case.