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
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.
- All the nodes on the left of a current node has a value less than current node.
- 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
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
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
