Python

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.
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:

Related Post
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,761 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

K

Share
Tags: Programming Python Python Data Structure

Recent Posts

  • Programming

Mastering Print Formatting in Python: A Comprehensive Guide

In Python, the print() function is a fundamental tool for displaying output. While printing simple…

8 months ago
  • Programming

Global Variables in Python: Understanding Usage and Best Practices

Python is a versatile programming language known for its simplicity and flexibility. When working on…

8 months ago
  • Programming

Secure Your Documents: Encrypting PDF Files Using Python

PDF (Portable Document Format) files are commonly used for sharing documents due to their consistent…

8 months ago
  • Programming

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

PDF (Portable Document Format) files are widely used for document exchange due to their consistent…

8 months ago
  • Programming

Boosting Python Performance with Cython: Optimizing Prime Number Detection

Python is a high-level programming language known for its simplicity and ease of use. However,…

8 months ago
  • Programming

Using OOP, Iterator, Generator, and Closure in Python to implement common design patterns

Object-Oriented Programming (OOP), iterators, generators, and closures are powerful concepts in Python that can be…

8 months ago

This website uses cookies.