Python: Binary Search Tree

A binary search tree with the usual preorder, postorder, inorder, and per level traversals:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
class Node(object):
        def __init__(self,value):
                self.value = value
                self.left = None
                self.right = None

class BinaryTree(object):
        def __init__(self):
                print "Creating tree"
                self.root = None
                self.nodeCount = 0
       
        def addValue(self, value):
                self.root = self.__addValue(self.root,value)
       
        def __addValue(self,node,value):
                if node == None:
                        self.nodeCount = self.nodeCount +1
                        return Node(value)
                elif value > node.value:
                        node.right = self.__addValue(node.right, value)
                elif value < node.value:
                        node.left = self.__addValue(node.left,value)
                return node
       
        def addValues(self,valuesList):
                for val in valuesList:
                        self.__addValue(self.root,val)
       
        def inOrderPrint(self):
                self.__inOrderPrint(self.root)

        def __inOrderPrint(self,node):
                if node == None:
                        return
                else:
                        self.__inOrderPrint(node.left)
                        print node.value,
                        self.__inOrderPrint(node.right)

        def printPreorder(self):
                if self.root == None:
                        print "Empty Tree"
                        return
                stack = [self.root]
                while stack != []:
                        curr = stack.pop()
                        print curr.value
                        if curr.right != None:
                                stack.append(curr.right)
                        if curr.left != None:
                                stack.append(curr.left)

        def printPostOrder(self):
                if self.root == None:
                        print "Empty Tree"
                        return
                explored = []
                frontier = [self.root]
                while frontier != []:
                        curr = frontier.pop()
                        if curr.left == None and curr.right == None:
                                print curr.value
                                continue
                        if explored.count(curr) != 0:
                                print curr.value
                                continue
                        frontier.append(curr)
                        explored.append(curr)
                        if curr.right != None:
                                frontier.append(curr.right)
                        if curr.left != None:
                                frontier.append(curr.left)


        def printInLevels(self):
                if self.root == None:
                        print "Empty Tree"
                        return
                currLevel = [self.root]
                nextLevel = []
                level = 0
                while currLevel != []:
                        print "level: " + str(level)
                        level += 1
                        while currLevel != []:
                                curr = currLevel.pop(0)
                                print curr.value,
                                if curr.left != None :
                                        nextLevel.append(curr.left)
                                if curr.right != None:
                                        nextLevel.append(curr.right)
                        currLevel = nextLevel
                        nextLevel = []


tree = BinaryTree()
tree.addValue(5)
tree.addValue(1)
tree.addValue(8)
tree.addValues([3,44,5,1,-2,4,23,4,0,-12])
tree.inOrderPrint()
tree.printInLevels()
tree.printPreorder()
tree.printPostOrder()

otherTree = BinaryTree()
otherTree.inOrderPrint()
otherTree.printInLevels()