Preorder and Postorder Traversal of binary tree in Python

by

Posted on 02 September 2018

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("\n")
    node.pre_order(root_node)
    sys.stdout.write("\n")
    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

If You Love this article, You Should Consider:

  • Like us on Facebook
  • Follow us on Instagram
  • Follow us on Twitter
  • Subscribe to our Newsletter.
  • Let us know your suggestions and queries in the comments below.

Thank you for your Love and Support

Share your thoughts

Search
Adverstisement
Adverstisement