Depth and Breadth First Tree Traversals

tree_search.py

from collections import deque

class Node(object):
    left = None
    right = None
    value = None

    def __init__(self, left, right, value):
        self.left = left
        self.right = right
        self.value = value

    def __repr__(self):
        s = set([self.left, self.right])
        s.discard(None)

        return "[ value: {}, children: {} ]".format(self.value, len(s))

# The Tree
#      1
#    /   \
#   2     3
#  /     / \
# 4     5   6

# Build Tree

# Bottom
four = Node(None, None, 4)
five = Node(None, None, 5)
six = Node(None, None, 6)

# Middle
two = Node(four, None, 2)
three = Node(five, six, 3)

# Top
one = Node(two, three, 1)

# Depth First
def process_node(node):

    # base
    if not node:
        return

    left = node.left
    right = node.right
    value = node.value

    print value

    process_node(left)
    process_node(right)

    return

print '-------------------------'
print "Depth First:"
print '-------------------------'
process_node(one)

def process_node_into_queue(q, node):
    if not node:
        return q

    q.append(node.left)
    q.append(node.right)

    return q

def breadth_first_traverse(node):

    queue = deque([one])

    while len(queue) != 0:
        node = queue.popleft()

        if node:
            print node.value

            if node.left or node.right:
                queue = process_node_into_queue(queue, node)
        else:
            print node

print ''
print '-------------------------'
print "Breadth First:"
print '-------------------------'
breadth_first_traverse(one)