Preorder and Postorder Traversal of binary tree in Python

As you know trees are non-linear data structures so there are many different ways to traverse them you can either visit the root node first and then visit the left subtree or the right subtree first or you can traverse level by level, there are many possible ways to traverse a tree.

In this tutorial, we will learn how to implement the following Tree Traversal techniques for a Binary tree in python:

  • Inorder traversal (Left, Root, Right)
  • Postorder traversal (Left, Right, Root)
  • Preorder traversal (Root, Left, Right)

Let’s take a simple example for each of the above traversal technique.

        4      / \     /   \   5      7  / \      3   1   

The inorder traversal for the above tree will be [3, 5, 1, 4, 7].
The postorder traversal for the above tree will be [3, 1, 5, 7, 4].
The inorder traversal for the above tree will be [4, 5, 3, 1, 7].

Inorder traversal of a Binary tree in python

Algorithm for inorder traversal

  • traverse the left subtree in inorder.
  • Visit the root node.
  • traverse the right subtree in inorder.

Now let’s write a simple recursive function for inorder traversal and add it to our Node class (read the tutorial on Binary tree in python).

def in_order(self, root):       if root is not None:           self.in_order(root.get_left) #traverse left subtree           sys.stdout.write(str(root.get_value)+" ") #visit root           self.in_order(root.get_right) #traverse right subtree

Postorder traversal of a Binary tree in python

Algorithm for postorder traversal

  • traverse the left subtree in postorder.
  • traverse the right subtree in postorder.
  • Visit the root node.
def post_order(self, root):       if root is not None:           self.post_order(root.get_left)           self.post_order(root.get_right)           sys.stdout.write(str(root.get_value)+" ")

Preorder traversal of a Binary tree in python

Algorithm for postorder traversal

  • Visit the root node.
  • traverse the left subtree in postorder.
  • traverse the right subtree in postorder.
def pre_order(self, root):       if root is not None:           sys.stdout.write(str(root.get_value)+" ")           self.pre_order(root.get_left)           self.pre_order(root.get_right)

now let’s see the complete code for our Binary Tree Traversal

import sys  class Node(object):    def __init__(self):       self.left = None       self.right = None       self.value = None   @property   def get_value(self):       return self.value    @property   def get_left(self):       return self.left    @property   def get_right(self):       return self.right    @get_left.setter   def set_left(self, left_node):       self.left = left_node   @get_value.setter   def set_value(self, value):       self.value = value   @get_right.setter   def set_right(self, right_node):       self.right = right_node      def create_tree(self):       _node = Node() #creating new node.       _x = input("Enter the node data(-1 for null)")       if(_x == str(-1)): #for defining no child.           return None       _node.set_value = _x #setting the value of the node.       print("Enter the left child of {}".format(_x))       _node.set_left = self.create_tree() #setting the left subtree       print("Enter the right child of {}".format(_x))       _node.set_right = self.create_tree() #setting the right subtree.        return _node    def pre_order(self, root):       if root is not None:           sys.stdout.write(str(root.get_value)+" ")           self.pre_order(root.get_left)           self.pre_order(root.get_right)    def post_order(self, root):       if root is not None:           self.post_order(root.get_left)           self.post_order(root.get_right)           sys.stdout.write(str(root.get_value)+" ")    def in_order(self, root):       if root is not None:           self.in_order(root.get_left)           sys.stdout.write(str(root.get_value)+" ")           self.in_order(root.get_right)     if __name__ == '__main__':   node = Node()   root_node = node.create_tree()   node.post_order(root_node)   sys.stdout.write("")   node.pre_order(root_node)   sys.stdout.write("")   node.in_order(root_node) 

Output

Enter the node data(-1 for null)4 Enter the left child of 4 Enter the node data(-1 for null)5 Enter the left child of 5 Enter the node data(-1 for null)3 Enter the left child of 3 Enter the node data(-1 for null)-1 Enter the right child of 3  Enter the node data(-1 for null)-1 Enter the right child of 5 Enter the node data(-1 for null)1 Enter the left child of 1 Enter the node data(-1 for null)-1 Enter the right child of 1 Enter the node data(-1 for null)-1 Enter the right child of 4 Enter the node data(-1 for null)7 Enter the left child of 7 Enter the node data(-1 for null)-1 Enter the right child of 7 Enter the node data(-1 for null)-1 3 1 5 7 4 4 5 3 1 7 3 5 1 4 7

Preorder and Postorder Traversal of binary tree in Python
02 September 2018

Binary Tree in Python
02 September 2018

Image Sharpening by High Pass Filter using Python and OpenCV
17 August 2018

Explaining Register variables in C with examples
17 August 2018

C program to generate all combinations of N-Bit Binary String
10 July 2018

Data Autosave System using PHP, MySQL and AJAX
06 July 2018

Понравилась статья? Поделиться с друзьями:
Добавить комментарий