#Tree data structure and traversals

class node:

def __init__(self):

self.data = None

self.left = None

self.right = None

def setData(self, data):

self.data = data

def setLeft(self, left):

self.left = left

def setRight(self, right):

self.right = right

def getData(self):

return self.data

def getLeft(self):

return self.left

def getRight(self):

return self.right

def createNode(data):

newNode = node()

newNode.setData(data)

return newNode

def addLeft(data, root):

lnode = createNode(data)

root.setLeft(lnode)

return lnode

def addRight(data, root):

rnode = createNode(data)

root.setRight(rnode)

return rnode

def inorder(root):

if root == None:

return

#Go left

inorder(root.getLeft())

print root.getData()

#Go right

inorder(root.getRight())

def postorder(root):

if root == None:

return

#Left

postorder(root.getLeft())

#Right

postorder(root.getRight())

print root.getData()

def preorder(root):

if root == None:

return

print root.getData()

#Left

preorder(root.getLeft())

#Right

preorder(root.getRight())

def diameter(root, h):

if root == None:

return h

left = diameter(root.getLeft(), h+1)

right = diameter(root.getRight(), h+1)

print "root is "

print root.getData()

print "height so far"+str(left)

if(left > right):

return left+1

return right+1

q = []

def levelorder(root):

global q

if root == None:

return

if(root.getLeft() != None):

q.append(root.getLeft().getData())

if (root.getRight() != None):

q.append(root.getRight().getData())

levelorder(root.getLeft())

levelorder(root.getRight())

#Main Program

root = createNode(1)

node1= addLeft(2, root)

node2 = addRight(3, root)

node3 = addLeft(4, node1)

node4 = addRight(5, node1)

node5 = addLeft(6, node2)

node6 = addRight(7, node2)

inorder(root)

print "\n\n"

postorder(root)

print "\n\n"

preorder(root)

q.append(root.getData())

levelorder(root)

print q

print "\n\n\n"

print "Diameter = "+str(diameter(root, 0))