Binary Tree Data Structure in Python

A binary tree is a hierarchical data structure which has at most two child nodes, i.e no node in the tree can have a degree greater than two. For a binary tree, we distinguish between the subtree on the left and right as left subtree and right subtree respectively.

• Binary Trees are mostly used to store natural hierarchical data.
• They provide moderate search, insertion and deletion speed.

In the previous tutorial, we went through file handling in python and in this tutorial we are going to implement Tree Data Structure in Python. So let’s get started.

Step – 1

We represent a Binary Tree by a pointer to the topmost node in tree. If the tree is empty, then value of root is NULL.
A Tree node contains following parts:

1. Data
2. Left Child
3. Right Child

Let’s see an example by implementing this Node:

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

Let’s analyze this code snippet before we go ahead.

• We made a Node class and modified the __init__ method (constructor).
• self is an object of the class Node
• The right and left object variable will point to the right and left child respectively. (if exists)
• val variable is passed in the constructor.

Step – 2

Now we need methods to check if the childs are empty or not:

class Node:
    def __init__(self, val):
        self.right = None
        self.left = None
        self.data = val
        
    def is_empty_lchild(self):
        if self.left == None:
            return True
        return False
    
    def is_empty_rchild(self):
        if self.right == None:
            return True
        return False

• is_empty_lchild(self) returns True if the self-object’s left is empty else it returns False.
• is_empty_rchild(self) returns True if the self-object’s right is empty else it returns False.

Finalization:

Now that we have finalized the ingredients let’s finalize the recipe.

class Node:
    def __init__(self, val):
        self.right = None
        self.left = None
        self.data = val
        
    def is_empty_lchild(self):
        if self.left == None:
            return True
        return False
    
    def is_empty_rchild(self):
        if self.right == None:
            return True
        return False
        
vals = [x for x in range(1, 10)]

# setting root code
root = Node(0)
x = root
for i in vals:
    if x.is_empty_lchild():
        x.left = Node(i)
        print('left')
    elif x.is_empty_rchild():
        x.right = Node(i)
        print('right')
        x = x.left

• First, we set the root node.
• Then we set the value depending on which child is Empty.
• When both the children are filled we made the x = x.left
• There are various ways to insert values in a Binary Tree. Stay tuned we will be covering them all in the next tutorials.
• Subscribe to our newsletter to never miss updates.

Checking Our Code:

>>>root.data
Out[16]: 0

>>>root.left.data
Out[17]: 1

>>>root.right.data
Out[18]: 2

>>>root.left.left.data
Out[19]: 3

>>>root.left.right.data
Out[20]: 4