"""
Learning Goals:
 - Identify whether a tree is a binary search tree
 - Search for values in BSTs using binary search
 - Analyze the efficiency of binary search on a balanced vs. unbalanced BST
 - Search for values in graphs using breadth-first search and depth-first search
 - Analyze the efficiency of BFS and DFS on a graph
"""

t = { "contents" : 3,
      "left" : { "contents" : 1,
                 "left" : None,
                 "right" : { "contents" : 2,
                             "left" : None,
                             "right" : None } },
      "right" : { "contents" : 5,
                  "left" : { "contents" : 4,
                             "left" : None,
                             "right" : None },
                  "right" : { "contents" : 8,
                              "left" : { "contents" : 6,
                                         "left" : None,
                                         "right" : None },
                              "right" : None } } }

def linearSearch(t, target):
    if t == None:
        return False
    elif t["contents"] == target:
        return True
    else:
        leftSide = linearSearch(t["left"], target)
        rightSide = linearSearch(t["right"], target)
        return leftSide or rightSide

print("Linear 4:", linearSearch(t, 4))
print("Linear 10:", linearSearch(t, 10))

###

def binarySearch(t, target):
    if t == None:
        return False
    elif t["contents"] == target:
        return True
    elif target < t["contents"]:
        leftSide = binarySearch(t["left"], target)
        return leftSide
    else: # target > t["contents"]
        rightSide = binarySearch(t["right"], target)
        return rightSide

print("Binary 4:", binarySearch(t, 4))
print("Binary 10:", binarySearch(t, 10))

###

g = { "A" : [ "B", "D", "F" ],
      "B" : [ "A", "E" ],
      "C" : [ ],
      "D" : [ "A", "E" ],
      "E" : [ "A", "B", "D" ],
      "F" : [ "A" ]
    }

def breadthFirstSearch(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]

        if next == target: # If it's what we're looking for- we're done!
            return True
        else: # Otherwise, add unvisited neighbors
            for node in g[next]:
                if node not in visited and node not in nextNodes: # Not seen before
                    nextNodes = nextNodes + [ node ] # Add to the BACK of the list

        nextNodes.remove(next)
        visited.append(next) # We've visited the node now
    return False

print("Breadth A-E", breadthFirstSearch(g, "A", "E"))
print("Breadth A-C", breadthFirstSearch(g, "A", "C"))

###

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]

        if next == target: # If it's what we're looking for- we're done!
            return True
        else: # Otherwise, add unvisited neighbors
            for node in g[next]:
                if node in nextNodes: # seen before, but higher-priority now
                    nextNodes.remove(node)
                if node not in visited and node not in nextNodes: # Not seen before
                    nextNodes = [ node ] + nextNodes # Add to the FRONT of the list
        nextNodes.remove(next)
        visited.append(next) # We've visited the node now
    return False

print("Depth A-E", depthFirstSearch(g, "A", "E"))
print("Depth A-C", depthFirstSearch(g, "A", "C"))