Trees and Graphs

Binary Search Tree


In [1]:
class TreeNode(object):
    """
    """
    def __init__(self,x,left=None,right=None):
        self.val = x
        self.left = left
        self.right = right
                
    def __str__(self):
        return "%d" % self.val
                    

def insert(root, data):

    if not root:
        root = TreeNode(data)        
    else:
        if data < root.val:
            if root.left is None:
                root.left = TreeNode(data)        
            else:
                insert(root.left,data)
        else:
            if root.right is None:
                root.right = TreeNode(data) 
            else:
                insert(root.right,data)
Create tree

In [42]:
head = TreeNode(8)

insert(head, 3)
insert(head, 10)
insert(head, 1)
insert(head, 6)
insert(head, 4)
insert(head, 7)
insert(head, 14)
insert(head, 13)

Traverse tree


In [57]:
print " BFS: \t", 
BFS(head)


print "\n\n recursivePreorder: \t",
recursivePreorder(head)
print "\n recursiveInorder: \t",
recursiveInorder(head)
print "\n recursivePostorder: \t",
recursivePostorder(head)

print "\n\n iterativePreorder: \t",
iterativePreorder(head)
print "\n iterativeInorder: \t",
iterativeInorder(head)
print "\n iterativePostorder: \t",
iterativePostorder3(head)


 BFS: 	8 3 10 1 6 14 4 7 13 

 recursivePreorder: 	8 3 1 6 4 7 10 14 13 
 recursiveInorder: 	1 3 4 6 7 8 10 13 14 
 recursivePostorder: 	1 4 7 6 3 13 14 10 8 

 iterativePreorder: 	8 3 1 6 4 7 10 14 13 
 iterativeInorder: 	1 3 4 6 7 8 10 13 14 
 iterativePostorder: 	1 4 7 6 3 13 14 10 8

In [52]:
def BFS(root):        
    
    queue = [root]
    
    while queue:
        node = queue.pop()
        if node.left is not None: 
            queue.insert(0,node.left)
        if node.right is not None: 
            queue.insert(0,node.right)
        
        print node.val,
                      
def recursivePreorder(root):        

    if root is None:
        return
        
    print root.val,
    recursivePreorder(root.left)
    recursivePreorder(root.right)   
    
def recursiveInorder(root):        

    if root is None:
        return
        
    recursiveInorder(root.left)
    print root.val,
    recursiveInorder(root.right)
    
def recursivePostorder(root):        

    if root is None:
        return
        
    recursivePostorder(root.left)
    recursivePostorder(root.right)    
    print root.val,
    
def iterativePreorder(root):
    
    if root is None:
        return
    
    stack = [root]
    current = root
    
    while stack:
        
        # Pop the top item from stack and print it
        node = stack.pop()
        print node.val,
         
        # Note that right child is pushed first so that left
        # is processed first
        if node.right is not None:
            stack.append(node.right)
        if node.left is not None:
            stack.append(node.left)     
            
def iterativeInorder(root):           

    current = root 
    s = [] 
    done = 0
     
    while(len(s) >0  or current is not None):
         
        # Reach the left most Node of the current Node
        if current is not None:
             
            s.append(current)        
            current = current.left 
          
        # BackTrack from the empty subtree and visit the Node
        # at the top of the stack; however, if the stack is 
        # empty you are done
        else:
            current = s.pop()
            print current.val,         
            # We have visited the node and its left
            # subtree. Now, it's right subtree's turn
            current = current.right 
                
                
def iterativePostorder(root):           
    
    if root is None:
        return 
    
    stack = [root]
 
    while stack:
        temp = stack[-1]
        if(temp.left is None and temp.right is None):
            pop = stack.pop()
            print pop.val,
        else:
            if(temp.right is not None):
                stack.append(temp.right)
                temp.right = None                
            if(temp.left is not None):
                stack.append(temp.left)
                temp.left = None
    
        
def peek(stack):
    if len(stack) > 0:
        return stack[-1]
    
#http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/    
def iterativePostorder2(root):
         
    # Check for empty tree
    if root is None:
        return
 
    stack = []
     
    while(True):
         
        while (root):
            # Push root's right child and then root to stack
            if root.right is not None:
                stack.append(root.right)
            stack.append(root)
            # Set root as root's left child
            root = root.left
         
        # Pop an item from stack and set it as root
        root = stack.pop()
 
        # If the popped item has a right child and the
        # right child is not processed yet, then make sure
        # right child is processed before root
        if (root.right is not None and
            peek(stack) == root.right):
            stack.pop() # Remove right child from stack 
            stack.append(root) # Push root back to stack
            root = root.right # change root so that the 
                             # righ childis processed next
 
        # Else print root's data and set root as None
        else:
            print root.val,
            root = None
 
        if (len(stack) <= 0):
                break        
        
#http://www.geeksforgeeks.org/iterative-postorder-traversal/        
def iterativePostorder3(root): 
 
    if root is None:
        return         
     
    # Create two stacks 
    s1 = []
    s2 = []
     
    # Push root to first stack
    s1.append(root)
     
    # Run while first stack is not empty
    while (len(s1) >0):
         
        # Pop an item from s1 and append it to s2
        node = s1.pop()
        s2.append(node)
     
        # Push left and right children of removed item to s1
        if node.left is not None:
            s1.append(node.left)
        if node.right is not None :
            s1.append(node.right)
 
        # Print all eleements of second stack
    while(len(s2) > 0):
        node = s2.pop()
        print node.val,

Find path algorithms


In [15]:
graph = {'A': ['B', 'C'],
         'B': ['C', 'D'],
         'C': ['D'],
         'D': ['C','F'],
         'E': ['F'],
         'F': ['C']}

print "One path: \t", find_path(graph,'A', 'D')
print "Shortest path: \t", find_min_path(graph,'A', 'D')
print "All paths: \t", find_all_paths(graph,'A', 'D')


One path: 	['A', 'B', 'C', 'D']
Shortest path: 	['A', 'C', 'D']
All paths: 	[['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]

In [3]:
def find_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not graph.has_key(start):
        return None
    for node in graph[start]:
        if node not in path:
            newpath = find_path(graph, node, end, path)
            if newpath: return newpath
    return None

def find_all_paths(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    if not graph.has_key(start):
        return []
    
    all_paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                all_paths.append(newpath)

    return all_paths

def find_min_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not graph.has_key(start):
        return None
    
    optimal_path = None
    for node in graph[start]:
        if node not in path:
            newpath = find_path(graph, node, end, path)
            if newpath:
                if not optimal_path or len(newpath)<len(optimal_path): 
                    optimal_path = newpath
                                
    return optimal_path