Test difference in speed and memory usage of DFS and BFS.

tree.py

import time,sys 
from random import randint

class node():
    def __init__(self, child1, child2, data):
        self.left = child1
        self.right = child2
        self.data = data
    def __str__(self):
        return str(self.data)
    
    def print_tree(self):
        import networkx as nx
        G=nx.Graph()
        queue = [self]
        while len(queue) != 0:
            current = queue.pop(0)
            G.add_node(current)
            if current.left is not None:
                G.add_edge(current, current.left)
                queue.append(current.left)

            if current.right is not None:
                G.add_edge(current, current.right)
                queue.append(current.right)
        import matplotlib.pyplot as plt
        nx.draw_spectral(G)
        plt.show()


def buildTree(nr=10):
    if nr == 0: 
        return None
    return node(buildTree(nr-1), buildTree(nr-1), randint(0, 99))

def BFS(value, root):
    queue = [root]
    maxlen = 1
    iterations = 0
    while len(queue) != 0:
        iterations += 1
        current = queue.pop(0)
        if current.data == value: 
            break
        else:
            if current.left is not None:
                queue.append(current.left)
            if current.right is not None:
                queue.append(current.right)
        if len(queue) > maxlen: 
            maxlen = len(queue)
    print "Bredth first search"
    print "-------------------"
    print "Max length of data: " + str(maxlen)
    print "Found data in " + str(iterations) + " iterations"
    

def DFS(value, root):
    stack = [root]
    maxlen = 1
    iterations = 0
    while len(stack) != 0:
        iterations += 1
        current = stack.pop()
        if current.data == value: 
            break
        else:
            if current.left is not None:
                stack.append(current.left)
            if current.right is not None:
                stack.append(current.right)
        if len(stack) > maxlen: 
            maxlen = len(stack)
    print "Depth first search"
    print "------------------"
    print "Max length of data: " + str(maxlen)
    print "Found data in " + str(iterations) + " iterations"

if __name__ == "__main__":
    if len(sys.argv[1]) == 2 and (sys.argv[1] == "-h" or sys.argv[1] == "--help"):
        print "python tree.py <depth-of-tree> <search-for-this-nr> [-v]"
        print "-v \tVisualize graph."
        print "Data is between 0 and 99"
        exit()


    if len(sys.argv) < 3: 
        size = 20
        search_for = 19
    else:
        size = int(sys.argv[1])
        search_for = int(sys.argv[2])
    print "Tree size " + str(size)
    print "Searching for " + str(search_for)
    print "Constructing tree..."
    root = buildTree(size)
    print "Done"
    print ""

    t = time.time()
    BFS(search_for, root)
    print "It took: " +str(t - time.time())
    print ""
    t = time.time()

    DFS(search_for, root)

    print "It took: " +str(t - time.time())
    if "-v" in sys.argv:
        root.print_tree()

Note that the trees are binary!

Here is some sample output

thalia:python christopherkack$ python tree.py 10 22 
Tree size 10
Searching for 22
Constructing tree...
Done

Bredth first search
-------------------
Max length of data: 47
Found data in 47 iterations
It took: -0.000123023986816

Depth first search
------------------
Max length of data: 10
Found data in 297 iterations
It took: -0.000355005264282
thalia:python christopherkack$ python tree.py 10 22 
Tree size 10
Searching for 22
Constructing tree...
Done

Bredth first search
-------------------
Max length of data: 50
Found data in 50 iterations
It took: -0.000104904174805

Depth first search
------------------
Max length of data: 10
Found data in 14 iterations
It took: -5.29289245605e-05
thalia:python christopherkack$ python tree.py 10 22 
Tree size 10
Searching for 22
Constructing tree...
Done

Bredth first search
-------------------
Max length of data: 35
Found data in 35 iterations
It took: -7.89165496826e-05

Depth first search
------------------
Max length of data: 10
Found data in 43 iterations
It took: -8.79764556885e-05