Binary Tree Traversal

from collections import deque

class Node:

    left , right, data = None, None, 0

 

    def __init__(self, data):

        # initializes the data members

        self.left = None

        self.right = None

        self.data = data

class BTree:

    def __init__(self):

        # initializes the root member

        self.root = None

 

    def addNode(self, data):

        # creates a new node and returns it

        return Node(data)

    def insert(self, root, data):

        # inserts a new data

        if root == None:

            # it there isn't any data

            # adds it and returns

            return self.addNode(data)

        else:

            # enters into the tree

            if data <= root.data:

                # if the data is less than the stored one

                # goes into the left-sub-tree

                root.left = self.insert(root.left, data)

            else:

                # processes the right-sub-tree

                root.right = self.insert(root.right, data)

            return root

     

    def pre_order_traversal(self, root, result=[]):

        if root == None:

            pass

        else:

            result.append(root.data)

            self.pre_order_traversal(root.left, result)

            self.pre_order_traversal(root.right, result)

        return result

 

    def in_order_traversal(self, root, result=[]):

        if root == None:

            pass

        else:

            self.in_order_traversal(root.left, result)

            result.append(root.data)

            self.in_order_traversal(root.right, result)

        return result

    def post_order_traversal(self, root, result=[]):

        if root == None:

            pass

        else:

            self.post_order_traversal(root.left, result)

            self.post_order_traversal(root.right, result)

            result.append(root.data)

        return result

 

    # breadth first traversal

    def bfs_traversal(self, root):

        if root == None:       # empty tree

            return

        # keep a queue which will hold all the nodes

        q = deque([root])

        while len(q) != 0:     # keep going until queue is empty

            node = q.popleft()

            if node == None:

                break

         

            print node.data

            if node.left != None:

                q.append(node.left)

            if node.right != None:

                q.append(node.right)

if __name__ == "__main__":

    # create the binary tree

    BTree = BTree()

    # add the root node

    root = BTree.addNode(0)

 

    # ask the user to insert values

    for i in range(0, 3):

        data = int(raw_input("insert the node value for node %d: " % i))

        # insert values

        BTree.insert(root, data)

 

    result = BTree.in_order_traversal(root, result=[])

    print "Inorder Traversal  "

    print ", ".join(map(str, result))

 

    result = BTree.pre_order_traversal(root, result=[])

    print "Preorder Traversal "

    print ", ".join(map(str, result))

 

    result = BTree.post_order_traversal(root, result=[])

    print "PostOrder Traversal "

    print ", ".join(map(str, result))

 

    print "BFS Traversal "

    BTree.bfs_traversal(root)