Rabbit House

class TreeNode(object):
  value=None
  lchild=None 
  rchild=None
  visited=0
  def __init__(self):
    value=None
    lchild=None 
    rchild=None 
    visited=0
  def visit(self):
    print self.value,
    visited=1

class Queue(object):
  items=[]
  size=0
  def __init__(self):
    items=[]
    size=0
  def head(self):
    if self.items!=[]:
      return self.items[0]
  def inqueue(self,item):
    self.items.append(item)
    self.size=len(self.items)
  def outqueue(self):
    for i in range(len(self.items)-1):
      self.items[i]=self.items[i+1]
    self.items.pop()
    self.size=len(self.items)

def preOrder(root):
  if root:
    root.visit()
    preOrder(root.lchild)
    preOrder(root.rchild)

def postOrder(root):
  if root:
    preOrder(root.lchild)
    preOrder(root.rchild)
    root.visit()

def inOrder(root):
  if root:
    inOrder(root.lchild)
    root.visit()
    inOrder(root.rchild)

def DFS(root):
  if root:
    root.visited=1
    print root.value,
    if root.lchild:
      if root.lchild.visited==0:
        DFS(root.lchild)
    if root.rchild:
      if root.rchild.visited==0:
        DFS(root.rchild)

def DFS2(root):
  # Non-recurrsive
  # Use a stack
  s=[]
  if root:
    s.append(root)
  while(s!=[]):
    node=s[len(s)-1]
    print node.value,
    s.pop()
    if node.rchild:
      s.append(node.rchild)
    if node.lchild:
      s.append(node.lchild)
  print ""

def BFS(root):
  if root:
    if root.visited==0:
      root.visited=1
      print root.value,
    if root.lchild:
      if root.lchild.visited==0:
        root.lchild.visited=1
        print root.lchild.value,
    if root.rchild:
      if root.rchild.visited==0:
        root.rchild.visited=1
        print root.rchild.value,
    if root.lchild:
      BFS(root.lchild)
    if root.rchild:
      BFS(root.rchild)


def BFS2(root):
  # Non-recurrsive
  # Use a quene
  q=Queue()
  if root:
    q.inqueue(root)
  while(q.size!=0):
    node=q.head()
    print node.value,
    q.outqueue()
    if node.lchild:
      q.inqueue(node.lchild)
    if node.rchild:
      q.inqueue(node.rchild)
  print ""

A=TreeNode()
B=TreeNode()
C=TreeNode()
D=TreeNode()
E=TreeNode()
F=TreeNode()
A.value='A'
B.value='B'
C.value='C'
D.value='D'
E.value='E'
F.value='F'

A.lchild=B 
B.lchild=D 
A.rchild=C 
C.lchild=E 
C.rchild=F 

DFS2(A)
BFS2(A)

Traversal of Binary Tree