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 1,762 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
ProgrammingPythonPython Basic Tutorial

Mastering Print Formatting in Python: A Comprehensive Guide

ProgrammingPython

Global Variables in Python: Understanding Usage and Best Practices

ProgrammingPythonPython Basic Tutorial

Secure Your Documents: Encrypting PDF Files Using Python

ProgrammingPython

Creating and Modifying PDF Files in Python: A Comprehensive Guide with Code Examples

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.