Tree_traversals.py

#! /usr/bin/env python3

# Implementation of Tree traversals(preorder, inorder, postorder)

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

class Tree:
    def __init__(self):
        self.root = None

    def insert(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            self._insert(data, self.root)
    
    def _insert(self, data, cur_node):
        if data < cur_node.data:
            if cur_node.left is None:
                cur_node.left = Node(data)
            else:
                self._insert(data, cur_node.left)
        elif data > cur_node.data:
            if cur_node.right is None:
                cur_node.right = Node(data)
            else:
                self._insert(data, cur_node.right)
        else:
            print("Value already in tree!")
    
    def find(self, data):
        if self.root:
            is_found = self._find(data, self.root)
            if is_found:
                return True
            return False
        else:
            return None
    
    def _find(self, data, cur_node):
        if data > cur_node.data and cur_node.right:
            return self._find(data, cur_node.right)
        elif data < cur_node.data and cur_node.left:
            return self._find(data, cur_node.left)
        if data == cur_node.data:
            return True
    
    def print_tree(self):
        if self.root is not None:
            self._print_tree(self.root)

    def _print_tree(self, cur_node):
        if cur_node is not None:
            self._print_tree(cur_node.left)
            print(str(cur_node.data))
            self._print_tree(cur_node.right)
    
    def preorder_traversal(self):
        print("Preorder traversal")
        self._preorder_traversal(self.root)
    
    def _preorder_traversal(self, cur_node):
        if cur_node:
            print(str(cur_node.data))
            self._preorder_traversal(cur_node.left)
            self._preorder_traversal(cur_node.right)
    
    def inorder_traversal(self):
        print("Inorder traversal")
        self._inorder_traversal(self.root)

    def _inorder_traversal(self, cur_node):
        if cur_node:
            self._inorder_traversal(cur_node.left)
            print(str(cur_node.data))
            self._inorder_traversal(cur_node.right)
    
    def postorder_traversal(self):
        print("Postorder traversal")
        self._postorder_traversal(self.root)
    
    def _postorder_traversal(self, cur_node):
        if cur_node:
            self._postorder_traversal(cur_node.left)
            self._postorder_traversal(cur_node.right)
            print(str(cur_node.data))
    
    def levelorder_traversal(self):
        """
        also called breadth-first traversal
        level order traversal is achieved by using a queue.
        """
        print("Levelorder traversal")
        if self.root is None:
            return
        queue = []
        queue.append(self.root)
        while len(queue) > 0:
            print(queue[0].data)
            node = queue.pop(0)
            if node.left is not None:
                queue.append(node.left)
            if node.right is not None:
                queue.append(node.right)
        
    def reverse_levelorder_traversal(self):
        """
        Reverse levelorder traversal is achieved by using two stacks.
        """
        print("Reverse levelorder traversal")
        if self.root is None:
            return
        queue = []
        stack = []
        queue.append(self.root)
        while len(queue) > 0:
            node = queue.pop(0)
            stack.append(node)
            if node.right is not None:
                queue.append(node.right)
            if node.left is not None:
                queue.append(node.left)
        while len(stack) > 0:
            node = stack.pop()
            print(node.data)

if __name__ == "__main__":
    tree = Tree()
    tree.insert(5)
    tree.insert(3)
    tree.insert(7)
    tree.insert(2)
    tree.insert(4)
    tree.insert(6)
    tree.insert(8)
    tree.print_tree()
    tree.preorder_traversal()
    tree.inorder_traversal()
    tree.postorder_traversal()
    tree.levelorder_traversal()
    tree.reverse_levelorder_traversal()