Binary tree in Python

Updated April 1, 2023

Introduction to Binary tree in Python

A binary tree in Python is a nonlinear data structure used for data search and organization. The binary tree is comprised of nodes, and these nodes, each being a data component, have left and right child nodes. Unlike other data structures, such as, Arrays, Stack and Queue, Linked List which are Linear type data structures, whereas Trees are Hierarchical types of data structures. Binary search tree or BST in short, whose nodes each store keys greater than their left child nodes and less than all the right child nodes. As the data in a binary tree is organized, it allows operations like insertion, deletion, update and fetch. Let us dive deeper into the concepts related to the Binary tree and implement some of the examples using Python programming language.

Syntax:

The binary tree does not have any particular Syntax but has an Algorithm to follow in implementing Binary Tree.

Algorithm for Binary Tree in Python

Step 1: We need to create a Node class for Binary tree declaration. Creation of Node Constructor:

class BTNode:
	def __init__(self, key):
		self.val = key
		self.left = None
		self.right = None

Here, we can have key-value, but if there isn’t any value, the user can set it to None. Both child nodes left, and right can also be assigned to None.

Step 2: We can insert data. If the node does not have any value, the user can set a value and return it. If the user tries to insert any data that exists, we can simply return the value. If the given value is less than the node value and has a left node, then we need to call the insert method on the left child node.

Step 3: There are two useful helper functions, getMin, and getMax. These are simple recursive functions that traverse the edges of the tree to store the smallest or largest values.

Step 4: Delete operation is also a recursive function but returns a new state of the given node after a deletion operation. On deleting any child node, the parent node will set left or right data to None.

Illustration of Binary Tree

Binary tree consists of below components,

Data, Pointer to Left node & Pointer to Right node.

Node: Elementary unit of Binary Tree

Root: Root unit of a binary tree.

Leaf: Leaves of Binary tree which have nodes without children

Level: Root is of level 0, children of the root node are level 1, and grandchildren of the root node is level 2

Parent: Parent of Node that is one level above the node.

Child: Children of the node are nodes that are one level below the parent node.

Examples of Binary tree in Python

Below are the examples mentioned:

Example #1

Creation of Node class for Binary tree with Root node Assignment

Code:

class BTNode:
    def __init__(self, val):
        self.left = None
        self.right = None
        self.val = val
    def rootNode(self):
        print(self.val)
root = BTNode('A')
root.rootNode()

Output:

So here, we have created a Node class and assigned a Root node value ‘A.’

Example #2

Inserting nodes in Binary Tree

Code:

class BTNode:
    def __init__(self, val):
        self.leftNode = None
        self.rightNode = None
        self.val = val
    def insertNode(self, val):
        if self.val:
            if val < self.val: if self.leftNode is None: self.leftNode = BTNode(val) else: self.leftNode.insertNode(val) elif val > self.val:
                if self.rightNode is None:
                    self.rightNode = BTNode(val)
                else:
                    self.rightNode.insertNode(val)
        else:
            self.val = val
    def displayTree(self):
        if self.leftNode:
            self.leftNode.displayTree()
        print( self.val),
        if self.rightNode:
            self.rightNode.displayTree()
root = BTNode('A')
root.insertNode('B')
root.insertNode('C')
root.insertNode('D')
root.insertNode('E')
root.insertNode('F')
root.displayTree()

Output:

So here Root node is A, the left node will be B, and the right node will be C.

Example #3

Search value in Binary Tree

Code:

class BTNode:
    def __init__(self, val):
        self.leftNode = None
        self.rightNode = None
        self.val = val
    def insertNode(self, val):
        if self.val:
            if val < self.val: if self.leftNode is None: self.leftNode = BTNode(val) else: self.leftNode.insertNode(val) elif val > self.val:
                if self.rightNode is None:
                    self.rightNode = BTNode(val)
                else:
                    self.rightNode.insertNode(val)
        else:
            self.val = val
    def searchVal(self, data):
        if data < self.val: if self.leftNode is None: return str(data)+" is not Found in the Binary Tree" return self.leftNode.searchVal(data) elif data > self.val:
            if self.rightNode is None:
                return str(data)+" is not Found in the Binary Tree"
            return self.rightNode.searchVal(data)
        else:
            return str(self.val) + " is found in the Binary Tree"
root = BTNode('A')
root.insertNode('B')
root.insertNode('C')
root.insertNode('D')
root.insertNode('E')
root.insertNode('F')
print(root.searchVal('B'))
print(root.searchVal('b'))
print(root.searchVal('D'))

Output:

While searching for a value in Binary Tree, the node is traversed from left to right.

Types of Binary Tree

Below are the different types of Binary tree:

1. Full Binary Tree: Special type of Binary Tree where every parent node or an internal node has either 2 or no child nodes.
2. Perfect Binary Tree: A Binary tree in which each internal node has exactly two children and all leaf nodes at the same level.
3. Complete Binary Tree: It is the same as a Full Binary Tree, but all leaf nodes must be at the left, and every level must have both left and right child nodes. And the last leaf node should not have the right child.
4. Pathological Tree: The Binary Tree has a single child, i.e. either left node or right node.
5. Skewed Binary Tree: It is similar to a pathological tree in which the binary tree is either dominated by left or right nodes. And it has two types: Left Skewed Binary tree and Right Skewed Binary Tree.
6. Balanced Binary Tree: Type of Binary Tree in which difference between the height of left and right subtree for each child node is 0 or 1

Conclusion

With this, we shall conclude our topic, “Binary Tree in Python”. We have seen what a Binary tree is and its Algorithm. Seen few examples of How a Binary tree is created, how insertion is done, and how we can search the Binary Tree nodes and display them. There are also types of Binary Tree which we have explained above. There are other operations too, which can help us to understand the concept of Binary Tree completely.

Recommended Articles

This is a guide to Binary tree in Python. Here we discuss the introduction, algorithm and illustration of Binary tree in python along with different examples. You may also look at the following articles to learn more –

1. Insertion sort in Python
2. BinarySearch() in Java
3. Python String Contains
4. PySpark foreach