Spiral Traversal of a Binary Search Tree

BST_traversal.py

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


class BST:
    def __init__(self, root=None):
        self.root = root

    def insert(self, node, value):
        if node == None:
            node = Node(value)
        else:
            if value < node.value:
                self.insertLeft(node, value)
            else:
                self.insertRight(node, value)
        


    def insertLeft(self, node, value):
        if node.left == None:
            node.left = Node(value)
        else:
            if node.left.value >= value:
                self.insertLeft(node.left, value)
            else:
                tmp = node.left
                node.left = Node(value)
                node.left.left = tmp
    
    def insertRight(self, node, value):
        if node.right == None:
            node.right = Node(value)
        else:
            if node.right.value < value:
                self.insertRight(node.right, value)
            else:
                tmp = node.right
                node.right = Node(value)
                node.right.right = tmp

    def height(self, node):
        if not node:
            return 0

        return max(1 + self.height(node.left), 1 + self.height(node.right)) 


    def inOrder(self, node):
        if not node:
            return

        self.inOrder(node.left)
        print node.value
        self.inOrder(node.right)


    def levelOrder(self, node):
        height = self.height(self.root)
        for i in range(1, height + 1):
            self.printLevel(self.root, i)

    def printLevel(self, node, level):
        if not node:
            return
        if level == 1:
            print node.value
        else:
            self.printLevel(node.left, level-1)
            self.printLevel(node.right, level-1)

    def spiralOrder(self, node):
        height = self.height(self.root)
        flag = False
        for i in range(1, height + 1):
            self.printSpiral(self.root, i, flag)
            flag = not flag


    def printSpiral(self, node, level, flag):
        if not node:
            return
        if level == 1:
            print node.value
        else:
            if flag:
                self.printSpiral(node.right, level-1, flag)
                self.printSpiral(node.left, level-1, flag)
            else:
                self.printSpiral(node.left, level-1, flag)
                self.printSpiral(node.right, level-1, flag)


tree = BST(Node(4))
tree.insert(tree.root, 2)
tree.insert(tree.root, 1)
tree.insert(tree.root, 3)
tree.insert(tree.root, 7)
tree.insert(tree.root, 5)
tree.insert(tree.root, 6)

print "In Order"
tree.inOrder(tree.root)

print "Height of Tree"
print tree.height(tree.root)
print "Level Order"
tree.levelOrder(tree.root)
print "Spiral Order"
tree.spiralOrder(tree.root)