How to implement a binary tree class

A tree is a non-linear data type that represents a hierarchical structure composed of nodes connected by edges. Each node in a tree contains data and references to its child nodes. The topmost node in the tree is called the root, and it is the starting point for traversing the tree. Nodes in a tree are organized in levels, with each level representing a generation of nodes.

Let’s look at the following illustration to get a better understanding of the hierarchical structure of the tree:

The terms used in the tree illustration are explained below:

Node: It is a fundamental unit of a tree and holds data. It can have zero or more child nodes.
Root: It is the topmost node of the tree, serving as the entry point for traversing the structure. It has no parent.
Parent and Child: A node having a child node is called a parent node. Conversely, the node directly connected to a parent node is its child node.
Leaf: It is a node without any child nodes. It resides at the ends of the tree’s branches.
Edge/link: It represents a connection between nodes. It defines the relationship between a parent node and its child nodes.
Siblings: Nodes that have the same parent node in the tree are called siblings. They are always on the same level or depth within the tree.

Binary tree

Binary tree class

Now, we create another class that will encapsulate the operations and functionality of the binary tree. This class will have a reference to the root node and several methods of the binary tree, such as the creation and level order traversal of a binary tree.

Let’s walk through the implementation of one of the methods of binary tree class, the creation of a binary tree. It works as follows:

It starts by checking if the list of elements is empty. If it is, it returns NULL to indicate an empty tree. Otherwise, it creates the root node using the first element of the list.
A queue is created, and the root node is enqueued. The method iterates over the remaining elements of the list, starting from the second element. During each iteration:
- It dequeues a node from the queue and processes the next two elements in the list. If the first element is not NULL, it creates a new Node object for its left child, sets it as the left child of the current node, and enqueues it.
- It then moves to the next element in the list and checks if it exists and is not NULL. If so, it creates a new Node object for its right child, sets it as the right child of the current node, and enqueues it.

The process continues until all elements in the list have been processed.

Here’s an example of binary tree class implementation having the creation and level order traversal methods:

BinaryTree.py

TreeNode.py

from queue import Queue
from TreeNode import *
class BinaryTree:
    def __init__(self, nodes):
        self.root = self.createBinaryTree(nodes)
    def createBinaryTree(self, nodes):
        if len(nodes) == 0:
            return None
        # Create the root node of the binary tree
        root = TreeNode(nodes[0].data)
        # Create a queue and add the root node to it
        queue = Queue()
        queue.put(root)
        # Start iterating over the list of nodes starting from the second node
        i = 1
        while i < len(nodes):
            # Get the next node from the queue
            curr = queue.get()
            # If the node is not None, create a new TreeNode object for its left child,
            # set it as the left child of the current node, and add it to the queue
            if nodes[i] is not None:
                curr.left = TreeNode(nodes[i].data)
                queue.put(curr.left)
            i += 1
            # If there are more nodes in the list and the next node is not None,
            # create a new TreeNode object for its right child, set it as the right child
            # of the current node, and add it to the queue
            if i < len(nodes) and nodes[i] is not None:
                curr.right = TreeNode(nodes[i].data)
                queue.put(curr.right)
            i += 1
        # Return the root of the binary tree
        return root
    # Function to perform level order traversal of the binary tree
    def level_order_traversal(self):
                
        # Create a queue to store nodes during traversal
        queue = Queue()
        
        # Put the root node in the queue
        queue.put(self.root)
        
        # Continue traversal until the queue is empty
        while not queue.empty():
            # Get the current node from the queue
            curr = queue.get()
            
            # Print the data of the current node
            print(curr.data, end=' ')
            
            # Check if the current node has a left child
            if curr.left:
                # If yes, put the left child in the queue for further traversal
                queue.put(curr.left)
            
            # Check if the current node has a right child
            if curr.right:
                # If yes, put the right child in the queue for further traversal
                queue.put(curr.right)
        
        # Print a new line after traversal is complete
        print()

Binary Tree class

main.py

TreeNode.py

BinaryTree.py

from TreeNode import *
from BinaryTree import *
if __name__ == '__main__':
    
    # Create a list of list of TreeNode objects to represent binary trees
    ListOfTrees = [ [TreeNode(10), TreeNode(9), TreeNode(20), TreeNode(15), TreeNode(7)],
                    [TreeNode(7), TreeNode(9), TreeNode(10), TreeNode(15), TreeNode(20)],
                    [TreeNode(8), TreeNode(2), TreeNode(17), TreeNode(1), TreeNode(4), TreeNode(19), TreeNode(5)],
                    [TreeNode(7), TreeNode(3), TreeNode(4), TreeNode(1), TreeNode(3)],
                    [TreeNode(9), TreeNode(5), TreeNode(7), TreeNode(1), TreeNode(3)],
                    [TreeNode(9), TreeNode(7), None, None, TreeNode(1), TreeNode(8), TreeNode(10), None, TreeNode(12)]
    ]
    # Create the binary trees using the BinaryTree class
    inputTrees = []
    for listOfNodes in ListOfTrees:
        tree = BinaryTree(listOfNodes)
        inputTrees.append(tree)
    # Print the input trees
    x = 1
    for tree in inputTrees:
        print("Level order traversal of tree # ", x, sep = "")
        tree.level_order_traversal()
        x += 1
        print("-" * 75)

Creation of a binary tree and level order traversal

How to implement a binary tree class

Binary tree

Implementation of a binary tree

Node class

Binary tree class

Code example