import sys
class Node( object ):
def __init__ ( self , key ):
self.left = None
self.right = None
self.key = key
class BinarySearchTree( object ):
def __init__( self, ):
self.root = None
def find( self, current, key ):
while current:
if key < current.key:
current = current.left
elif key > current.key:
current = current.right
else:
return current
return False # null pointer means not found
def insert( self, key ):
if not self.root:
self.root = Node( key )
else:
current = self.root
while current:
if key < current.key:
if current.left:
current = current.left
else:
current.left = Node( key )
break;
elif key > current.key:
if current.right:
current = current.right
else:
current.right = Node( key )
break;
def size( self, current ):
if not current:
return 0
else:
left_size = self.size( current.left )
right_size = self.size( current.right )
return left_size + right_size + 1
def max_height( self , current ):
if not current:
return 0
else:
return max( self.max_height( current.left ), self.max_height( current.right ) ) + 1
def min_height( self , current ):
if not current:
return 0
else:
return min( self.min_height( current.left ), self.min_height( current.right ) ) + 1
def find_minimum( self, current ):
minimum = current
while current.left:
current = current.left
minimum = current
return minimum
def find_maximum( self, current ):
maximum = current
while current.right:
current = current.right
maximum = current
return maximum
def count( self, current, min, max ): # O(n) for full traversal
if not current:
return 0
else:
left_size = self.count( current.left, min, max )
right_size = self.count( current.right, min, max )
if current.key >= min and current.key <= max:
return left_size + right_size + 1
else:
return left_size + right_size
def count_in_range( self , inclusive_start, inclusive_end ): # O(n) for full traversal
from cStringIO import StringIO
old_stdout = sys.stdout
string_buffer = StringIO()
sys.stdout = string_buffer
self.in_order_traversal( self.root )
sys.stdout = old_stdout
result = string_buffer.getvalue()
string_buffer.close()
results = result.split(',')
count = 0
for key in results:
if key and int( key )>= inclusive_start and int( key ) <= inclusive_end:
count += 1
return count
def breadth( self , current ):
if not current:
return
from collections import deque
visited = deque()
unvisited = deque()
unvisited.append( current )
while len( unvisited ) > 0:
current = unvisited.popleft()
if current.left:
unvisited.append( current.left )
if current.right:
unvisited.append( current.right )
visited.append( current )
for node in visited:
print node.key,
def pre_order_traversal( self, current ): # root first
if not current:
return
sys.stdout.write( str( current.key ) + ',' )
self.pre_order_traversal( current.left )
self.pre_order_traversal( current.right )
def in_order_traversal( self, current ): # sorted list
if not current:
return
self.in_order_traversal( current.left )
sys.stdout.write( str( current.key ) + ',' )
self.in_order_traversal( current.right )
def post_order_traversal( self, current ): # root last
if not current:
return
self.post_order_traversal( current.left )
self.post_order_traversal( current.right )
sys.stdout.write( str( current.key ) + ',' )
def lowest_common_ancestor( self, current, key1, key2 ):
while current:
if current.key > key1 and current.key > key2: # both nodes in the left subtree
current = current.left
elif current.key < key1 and current.key < key2: # both nodes in the right subtree
current = current.right
else:
return current.key
if __name__ == '__main__':
empty = BinarySearchTree( )
print 'empty in order: ',
empty.in_order_traversal( empty.root )
print '\nempty size: ', empty.size( empty.root )
ASC = [ 0,1,2,3,4 ]
for i in xrange( len( ASC ) ):
empty.insert( ASC[ i ] )
print 'UNBALANCED: ',
print ' min height: ', empty.min_height( empty.root ),
print ' max height: ', empty.max_height( empty.root ),
print '\nunbalanced_complete pre order: ',
empty.pre_order_traversal( empty.root )
print '\n'
BALANCED_COMPLETE = [ 4, 2, 1, 3, 6, 5, 7 ]
balanced_complete = BinarySearchTree()
for i in xrange( len( BALANCED_COMPLETE ) ):
balanced_complete.insert( BALANCED_COMPLETE[ i ] )
print 'balanced_complete size: ', balanced_complete.size( balanced_complete.root )
print 'min height: ', balanced_complete.min_height( balanced_complete.root )
print 'max height: ', balanced_complete.max_height( balanced_complete.root )
print 'min: ', balanced_complete.find_minimum( balanced_complete.root ).key
print 'max: ', balanced_complete.find_maximum( balanced_complete.root ).key
print '\nbalanced_complete in order: ',
balanced_complete.in_order_traversal( balanced_complete.root )
print '\nbalanced_complete pre order: ',
balanced_complete.pre_order_traversal( balanced_complete.root )
print '\nbalanced_complete post order: ',
balanced_complete.post_order_traversal( balanced_complete.root )
print '\n count in range(0,5): ', balanced_complete.count_in_range( 0, 5 )
print 'count in range(0,5): ', balanced_complete.count( balanced_complete.root, 0, 5 )
balanced_complete.breadth( balanced_complete.root )
print
print 'lowest common ancestor of 2 and 7:', balanced_complete.lowest_common_ancestor( balanced_complete.root, 2, 7 ) # 4, the root
print 'lowest common ancestor of 5 and 7:', balanced_complete.lowest_common_ancestor( balanced_complete.root, 5, 7 ) # 6, their parent
# Min Common Ancestor: in order Subtree THEN post order ancestor compare