"""
Learning Goals:
 - Identify whether or not a tree is a binary search tree
 - Search for values in binary search trees using binary search
 - Understand how and why hashing makes it possible to search for values in O(1) time
 - Search for values in a hashtable using a specific hash function
 - Search for values in graphs using breadth-first search and depth-first search
"""

def search(t, target):
  if t == None:
    return False
  elif t["value"] == target:
    return True
  else:
    return search(t["left"], target) or \
           search(t["right"], target)

###

def binarySearch(t, target):
    if t == None:
        return False
    elif t["value"] == target:
        return True
    else:
        if target < t["value"]:
            return binarySearch(t["left"], target)
        else:
            return binarySearch(t["right"], target)

###

def breadthFirstSearch(g, start, target):
    # Set up two lists for visited nodes and to-visit nodes
    visited = [ ]
    frontier = [ start ]

    # Repeat while there are nodes to visit
    while len(nextNodes) > 0:
        next = nextNodes[0]
        nextNodes.pop(0)

        if next == target: # If it's what we're looking for- we're done!
            return True

        # Only expand this node if we haven't visited it before, to avoid repeats
        if next not in visited:
            visited.append(next)
            nextNodes = nextNodes + g[next]
    return False

###

def depthFirstSearch(g, start, target):
    # Set up two lists for visited nodes and to-visit nodes
    visited = [ ]
    nextNodes = [ start ]

    # Repeat while there are nodes to visit
    while len(nextNodes) > 0:
        next = nextNodes[0]
        nextNodes.pop(0)

        if next == target: # If it's what we're looking for- we're done!
            return True

        # Only check this node if we haven't visited it before, to avoid repeats
        if next not in visited:
            visited.append(next)
            nextNodes = g[next] + nextNodes
    return False