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.
It is a type of tree where each node has at most two children, referred to as the left child and the right child. The nodes in a binary tree have no fixed organization while forming subtrees. It is an unordered tree. The topmost node is called the root, and every node, except for the root, has a parent node.
To implement a binary tree, we start by creating a class or a structure to represent the nodes. Each node typically contains three components—the value or data it holds, a reference to the left child, and a reference to the right child.
Here’s an example of the implementation of node:
# Creating Node classclass TreeNode:def __init__(self, data):# Data or value a node holdsself.data = data# Reference to the left childself.left = None# Reference to the right childself.right = None
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:
from queue import Queuefrom 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 treeroot = TreeNode(nodes[0].data)# Create a queue and add the root node to itqueue = Queue()queue.put(root)# Start iterating over the list of nodes starting from the second nodei = 1while i < len(nodes):# Get the next node from the queuecurr = 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 queueif 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 queueif 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 treereturn root# Function to perform level order traversal of the binary treedef level_order_traversal(self):# Create a queue to store nodes during traversalqueue = Queue()# Put the root node in the queuequeue.put(self.root)# Continue traversal until the queue is emptywhile not queue.empty():# Get the current node from the queuecurr = queue.get()# Print the data of the current nodeprint(curr.data, end=' ')# Check if the current node has a left childif curr.left:# If yes, put the left child in the queue for further traversalqueue.put(curr.left)# Check if the current node has a right childif curr.right:# If yes, put the right child in the queue for further traversalqueue.put(curr.right)# Print a new line after traversal is completeprint()
Let’s take a look at the code example for the creation of a binary tree and its level order traversal:
from TreeNode import *from BinaryTree import *if __name__ == '__main__':# Create a list of list of TreeNode objects to represent binary treesListOfTrees = [ [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 classinputTrees = []for listOfNodes in ListOfTrees:tree = BinaryTree(listOfNodes)inputTrees.append(tree)# Print the input treesx = 1for tree in inputTrees:print("Level order traversal of tree # ", x, sep = "")tree.level_order_traversal()x += 1print("-" * 75)