Python Tree Data Structure Explained [Practical Examples]

Introduction to Tree Data structure in Python

A Tree is a non linear data structure in which nodes are connected in a hierarchical manner. Every tree has one root node that marks the access point of all the other nodes in the tree. So, a Tree is formed of one root node, and 0 or more child nodes. The trees are categorized into different types on the basis of their structure and type of data. They are Binary Tree, Binary Search Tree, AVL Tree, B Tree, B+ Tree, Expression Tree, etc.

The figure below shows the structure of Binary search Tree.
Binary search Tree

Advertisement

 

Binary Search Tree

Binary search tree is a special binary tree that consist of 0, 1 or 2 child nodes and follows certain rules while inserting the value in the node. The Binary search tree is a binary tree in which all the nodes follow the below mentioned properties.

  1. All the nodes on the left of a current node has a value less than current node.
  2. All the nodes on the right of a current node has a value greater than current node.

Here, we will see how to implement a binary search tree from scratch in Python.

 

Creating a node

In order to create a binary Python Tree Data Structure, we will have to first create a Node class that represents a single node. This Node class will have 3 class variables. The left variable pointing to the left child, the right variable pointing to the right child and the data variable containing the actual value for that node. The code below shows the class representing a node.

# Implementing Python Tree Data Structure
# Creating a class for node object
class Node(object):
    # Initializing to None
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

 

Implementing Insertion in Binary Search Tree

In order to insert a node in binary search tree, we need to make sure that none of the properties of binary search tree is violated while inserting a node.

Here, the each call to the insertion method will insert one node to a binary search tree. The first call to insertion will make that node as a root node. All the other insertions will take place considering the value of root node.
The code below shows the insertion function which places the node in a tree such that none of the properties of binary search tree is violated.

# Implementing Python Tree Data Structure
# Creating a class for node object
class Node(object):
    # Initializing to None
    def __init__(self):
        self.left = None
        self.right = None
        self.data = None

# Inserting a node in Binary search tree
def insertion(val):
    # Condition if this is a first node then it will be considered as a root
    if(root.data==None):
        print(val," Inserted as root")
        root.data=val
    # Else part will be executed for all the other insertions
    else:
        # Pointer to move around tree to search for a place of new node
        p=root
        
        # Creating a new node and writing a value in the data part
        n = Node()
        n.data=val
        
        # Iterating to search for an appropriate place of new node
        while(1):
            # if val is less than the current node p indicates that new node will be inserted on left subtree
            if(val<p.data):
                if(p.left==None):
                    print(val," Inserted on left of ",p.data)
                    p.left=n
                    break
                else:
                    p=p.left
            # if val is greater than the current node p indicates that new node will be inserted on right subtree
            else:
                if(p.right==None):
                    print(val," Inserted on right of",p.data)
                    p.right=n
                    break
                else:
                    p=p.right

root = Node()  
insertion(10)
insertion(5)
insertion(20)
insertion(30)
insertion(25)
insertion(2)
'''
           10
          /  \
         5   20
        /      \
       2       30
              /
             25
'''

Output

Advertisement
10  Inserted as root
5  Inserted on left of  10
20  Inserted on right of 10
30  Inserted on right of 20
25  Inserted on left of  30
2  Inserted on left of  5

 

Inorder Traversal on Binary Search Tree

Traversing a tree means iterating over all nodes in some sequence. As the tree is not a linear data structure, there will be more than one possible next node from a current node, so some nodes will be stored so that we can visit them later. The Inorder traversal is one of the depth first tree traversal methods. Here, while traversing a tree, whenever we come across a node for the first time, we recursively traverse to its left sub tree before printing the current node, and then recursively traverse to its right subtree thereafter.

Once insertion is done in binary search tree, we can add the recursive function given below to traverse a tree in inorder sequence.

# Implementing Python Tree Data Structure
# Function for inorder traversal of tree
def inorder(node):
    if node:
	# Traversing left subtree
        inorder(node.left)
	# Visiting node
        print(node.data)
	# Traversing right subtree
        inorder(node.right)

Output

2
5
10
20
25
30

 

Preorder Traversal on Binary Search Tree

Here, while traversing a tree, whenever we come across a node for the first time, we will visit the node then we recursively traverse to its left sub tree and then recursively traverse to its right subtree thereafter.

Once insertion is done in binary search tree, we can add the recursive function given below to traverse a tree in preorder sequence.

# Implementing Python Tree Data Structure
# Function for preorder traversal of tree
def preorder(node):
    if node:
	# Visiting node
        print(node.data)
        # Traversing left subtree
        inorder(node.left)
	# Traversing right subtree
        inorder(node.right)

Output

Advertisement
10
5
2
20
30
25

 

Postorder Traversal on Binary Search Tree

As the name suggest, we will visit the node once its left subtree and right subtree has been visited. While traversing a tree, whenever we come across a node for the first time, we recursively traverse to its left sub tree and then recursively traverse to its right subtree and finally visit the node.

Once insertion is done in binary search tree, we can add the recursive function given below to traverse a tree in postorder sequence.

# Implementing Python Tree Data Structure
# Function for postorder traversal of tree
def postorder(node):
    if node:
	# Traversing left subtree
        inorder(node.left)
	# Traversing right subtree
        inorder(node.right)
        # Visiting node
        print(node.data)

Output

2
5
25
30
20
10

 

Summary

The knowledge of Python Tree Data Structure is very useful while working on real time applications. In this tutorial, we covered creation, insertion and traversal on tree data structure with the sample code example. As per the requirement of an application, we can choose an appropriate traversal method to traverse a tree.

We learned in detail about this with an example. All in all, this tutorial, covers everything that you need to know in order to have a clear view on Python Tree Data Structure.

 

References

Classes in Python

Advertisement

 

Didn't find what you were looking for? Perform a quick search across GoLinuxCloud

If my articles on GoLinuxCloud has helped you, kindly consider buying me a coffee as a token of appreciation.

Buy GoLinuxCloud a Coffee

For any other feedbacks or questions you can either use the comments section or contact me form.

Thank You for your support!!

Leave a Comment

X