Binary Tree and its traversal using python.

After a long time I took a look in algorithms and data structure and what I wrote first in Binary Tree and its different traversal in C++. I have never written them in python so I tried to write one. And yes writing them down in python is lot more easier. So lets me first introduce you to the basic concepts of Binary tree then we will code Binary Tree and its traversal using python.

Binary Tree and its traversal using python.

Binary tree are the tree where one node can have only two child and cannot have more than two. Traversal means visiting all the nodes of the Binary tree. There are three types of traversal.

Lets take the below tree for example.

Binary Tree and its traversal using python.

 

Inorder traversal

In order traversal means visiting first left, then root and then right.

So the traversal of above tree would be 4 2 5 1 3

Pre Order Traversal

In this traversal we first visit root, then left, then right

It will be something like this 1 2 4 5 3

Post Order traversal

Here we first visit left, then right and then root.

It will be something like this 4 5 2 3 1

If you want to learn data structures in python you can read the below books.



These were the traversal now lets code it in python

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

def inOrder(root):
   if root:
       inOrder(root.left)
       print (root.data)
       inOrder(root.right)

def preOrder(root):
   if root:
       print (root.data)
       preOrder(root.left)
       preOrder(root.right)

def postOrder(root):
   if root:
       postOrder(root.left)
       postOrder(root.right)
       print (root.data)

#making the tree 
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print inOrder(root)
#4 2 5 1 3
print preOrder(root)
#1 2 4 5 3
print postOrder(root)
#4 5 2 3 1

So this is how you write the binary tree in Python.

Lets have a look at the script.

We made a class Node which represent the node of Binary tree. We initialize the node with data and left and right child as None.

When we add new child we simple use root.left or root.left.left to add a new child.

 

Now lets have a look at the traversal functions.

In all these functions we took advantage of recursion and passed the subtrees in the functions again to print in proper order. In Inorder function,  we first pass the left subtree to Inorder then print the node and then pass the right subtree. Thus made left, root and right. Similarly we did for the other two.

Here we took a look into how to code binary Tree and its traversal using python.

Read about Graphs and its implementation in python here.


Gaurav Yadav

Gaurav is cloud infrastructure engineer and a full stack web developer and blogger. Sportsperson by heart and loves football. Scale is something he loves to work for and always keen to learn new tech. Experienced with CI/CD, distributed cloud infrastructure, build systems and lot of SRE Stuff.

5 COMMENTS
  • Shaurya Rohatgi
    Reply

    Good article bro !

    Just one suggestion for function and variable names in python follow the convention – which is instead of using camel case like in Java separate words by ‘_’, so your function names become pre_order, post_order etc.

    Anyways, Keep it up ladke 🙂

    1. Gaurav Yadav
      Reply

      Thanks for the suggestion sir. Its just that I followed this convention and you can see its consistent overall.

  • Vijay
    Reply

    Nice bro, never thought that this would be so easy.

    1. Gaurav Yadav
      Reply

      Yup me too will be sharing more like this. Why don’t you have a look at coding a linked list in python https://www.learnsteps.com/algorithms-coding-linked-list-python/

  • srinithi
    Reply

    the output is correct but why does it print none after the tree traversals are printed
    my op goes like
    1
    2
    4
    5
    3
    None

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.