Top 10 Programming Languages to Learn in 2019

ProgrammingPythonPython Data Structures

Binary Tree Data Structure in Python

binary tree 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.
Binary Tree Python
Binary Tree

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.

Join 2,495 other subscribers

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

Related posts
Programming

Amazon Price Scraper and Auto Mailer Python App

ProgrammingPython

Top 10 Deep Learning frameworks in 2019 (with comparison)

ProgrammingPython

Python vs R - Data Visualization

Programming

Cython vs Python - Speed up your Python

Leave a Reply

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

Improve Your Python

...with a fresh 🐍 Python Trick 💌
code snippet every couple of days:
You can also contribute to PyBlog
Visit Contribute to Community

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

PyBlog will use the information you provide on this form to be in touch with you and to provide updates and marketing.