Tree/Binary Tree in Python

A tree is a non-linear data structure that has hierarchical relationships between its elements. It consists of nodes, connected by edges, that store data item. The arrangement of elements is such that the formation of a cycle is avoided.

The combination of nodes gives the tree its hierarchical data structure. Each node in a tree has two components: data and a link to its adjacent nodes. A node can have a parent node, a child node, or both.

In a linear data structure, the time complexity for performing operations increases with the increase in the data size. Since trees are non-linear data structures, operations such as insertion, deletion and traversal take significantly lesser time for execution.

The tree data structure provides the following advantages:

• Quicker and easier access to data.
• Store hierarchical data, like folder structure, organization structure, XML/HTML data.
• There are many different types of data structures,such as Binary Search Tree, AVL, Red Black Tree, and Trie, which perform better in various situations.

Tree Terminologies

Node

A node is a fundamental entity that makes up a tree. Each node contains a value and pointer to its child nodes. The root node is the topmost node of a tree.

The leaf node or external node is the last node of any path in the tree. They do not contain a link/pointer to child nodes. The node having at least one child node is called an internal node.

Edge/Branch

The edge/branch of a tree is the link between any two nodes. The edges are arranged in such a way that no cycle is formed between nodes. A path is the sequence of nodes along the edges of a tree.

Height, Depth and Degree of a Node

The height of a node is the number of edges from the node to the deepest leaf (i.e. the longest path from the node to a leaf node). The depth of a node is the number of edges from the root to the node. The degree of a node is the total number of branches of that node.

Depth and Height of a Tree

The height and depth of a tree are two equivalent terms. It is defined as the height of the root node or the depth of the deepest node.

Creation of Basic Tree in Python

To create a basic tree in python, we first initialize the “TreeNode” class with the data items and a list called “children”. Then, we will edit the “__str__” function to print the node values as if they were a tree. Lastly, we’ll create a function to add nodes to the tree.

For the creation of a basic tree, we have used a list as the fundamental storage data structure. Thus, we use the in-built append function to insert elements. The trick is to modify the “__str__” function in such a way that the print statement displays a tree-like structure.

#Class to implement basic tree data structure
class TreeNode:
    def __init__(self, data, children=[]):
        self.data = data
        self.children = children

    def __str__(self, level=0):
        ret = "  " * level + str(self.data) + "\n"
        for child in self.children:
            ret += child.__str__(level + 1)
        return ret

    def addChild(self, TreeNode):
        self.children.append(TreeNode)

tree = TreeNode('Drinks', [])
cold = TreeNode('Cold', [])
hot = TreeNode('Hot', [])
tree.addChild(cold)
tree.addChild(hot)
tea = TreeNode('Latte', [])
coffee = TreeNode('Mocha', [])
coke = TreeNode('Coke', [])
sprite = TreeNode('Sprite', [])
cold.addChild(coke)
cold.addChild(sprite)
hot.addChild(tea)
hot.addChild(coffee)
print(tree)

#Output
Drinks
  Cold
    Coke
    Sprite
  Hot
    Latte
    Mocha

Binary Tree

Binary Trees are hierarchical data structures in which each node has at most two children, often referred to as the left and right child. Binary trees are a prerequisite for more advanced trees like BST, AVL, Red-Black Trees.

Each node contains three elements:

• Pointer to left child
• Pointer to right child
• Data element

Types of Binary Tree

Full Binary Tree

A Full Binary Tree is a binary tree in which every node has 0 or 2 children. In other words, a full binary tree is the one in which all nodes have two children, except the leaf nodes.

Perfect Binary Tree

A Perfect Binary Tree is a binary tree in which all interior nodes have 2 children and all the leaf nodes have the same depth.

Complete Binary Tree

A Complete Binary tree is a binary tree in which every level, except possibly the last, is completely filled. All the nodes in a complete binary tree are as far left as possible.

Balanced Binary Tree

A Balanced Binary Tree is a binary tree that satisfies the following properties:

• The heights of the left and right subtrees differ by at most one.
• The left subtree is balanced.
• The right subtree is balanced.

Degenerate Tree

A Degenerate Tree is a binary tree in which each parent node has only one child node. A degenerate tree behaves like a linked list based on its structure.

Creation of Binary Tree built using Linked List

To create a binary tree using a linked list in python, we first need the linked list class which declares its functions. Then, we will create the binary tree class and create its associated functions based on the fundamental node class of the linked list.

We will use the queue data structure built using a linked list to implement functions such as traversal, searching, insertion, deletion, etc. We have dedicated an article for queue built using a linked list. For a detailed explanation of the Queue class below, refer to that article.

#Creating the Queue class using linked list
class Node:
    def __init__(self, value=None):
        self.value = value
        self.next = None

    def __str__(self):
        return str(self.value)


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def __iter__(self):
        node = self.head
        while node:
            yield node
            node = node.next

class Queue:
    def __init__(self):
        self.linkedList = LinkedList()

    def __str__(self):
        values = [str(x) for x in self.linkedList]
        return ' '.join(values)

    def enqueue(self, value):
        new_node = Node(value)
        if self.linkedList.head == None:
            self.linkedList.head = new_node
            self.linkedList.tail = new_node
        else:
            self.linkedList.tail.next = new_node
            self.linkedList.tail = new_node

    def isEmpty(self):
        if self.linkedList.head == None:
            return True
        else:
            return False

    def dequeue(self):
        if self.isEmpty():
            return "The Queue is empty."
        else:
            tempNode = self.linkedList.head
            if self.linkedList.head == self.linkedList.tail:
                self.linkedList.head = None
                self.linkedList.tail = None
            else:
                self.linkedList.head = self.linkedList.head.next
            return tempNode

    def peek(self):
        if self.isEmpty():
            return "The Queue is empty."
        else:
            return self.linkedList.head

    def delete(self):
        self.linkedList.head = None
        self.linkedList.tail = None

#Creation of the base Tree class
import QueueLinkedList as queue

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.leftChild = None
        self.rightChild = None

#Initializing a tree node
newTree = TreeNode("Drinks")

Time and Space Complexity for Creation

The time complexity for the creation of the basic Tree class is O(1) because it takes constant time to initialize the data components of the tree node. The space complexity is O(1) as well since no additional memory is required for initialization.

Operations on Binary Tree built using Linked List

One of the most important operations to perform on a Binary tree is traversal. Traversing a tree means visiting every node of the tree. In a binary tree, traversal can be performed in various ways:

PreOrder Traversal in Binary Tree

Pre-order traversal visits the current node before its child nodes. In a pre-order traversal, the root is always the first node visited.

Example:

PreOrder Traversal – N1 -> N2 -> N4 -> N8 -> N9 -> N5 -> N3 -> N6 -> N7

Implementation of PreOrder Traversal

For implementing pre-order traversal in a binary tree, the below code makes use of a recursive function preOrderTraversal. Initially, the root node is passed as an argument to this function.

If the root node is not empty, its content is displayed followed by calling the same recursive function with the left and right of the current node. The function preOrderTraversal terminates a recursion when the encountered node is found to be empty.

#Creating the PreOrder Function
def preOrderTraversal(root_node):
    if not root_node:
        return
    print(root_node.data)
    preOrderTraversal(root_node.leftChild)
    preOrderTraversal(root_node.rightChild)

#Initializing the Binary Tree
newTree = TreeNode("Drinks")
leftChild = TreeNode("Hot")
tea = TreeNode("Latte")
coffee = TreeNode("Mocha")
leftChild.leftChild = tea
leftChild.rightChild = coffee

rightChild = TreeNode("Cold")
coke = TreeNode("Coke")
sprite = TreeNode("Sprite")
rightChild.leftChild = coke
rightChild.rightChild = sprite

newTree.leftChild = leftChild
newTree.rightChild = rightChild

preOrderTraversal(newTree)

Output

Time and space Complexity

The time complexity for PreOrder traversal is O(N) because the function recursively visits all nodes of the tree. When we use a recursive function, it holds up memory in the stack so as to recognize its next call. Thus, the space complexity for PreOrder traversal is O(N).

InOrder Traversal in Binary Tree

In-order traversal means to visit the left branch, then the current node, and finally, the right branch.

Example:

InOrder Traversal – N8 -> N4 -> N9 -> N2 -> N5 -> N1 -> N6 -> N3 -> N7

Implementation of InOrder Traversal

For implementing in-order traversal in a binary tree, the below code makes use of a recursive function inOrderTraversal. Initially, the root node is passed as an argument to this function.

If the root node is not empty, a recursive call to the left child is made, followed by displaying the content of the current node, and then a recursive call to the right child is made. The function inOrderTraversal terminates a recursion when the encountered node is found to be empty.

#Creating the InOrder Function
def inOrderTraversal(root_node):
    if not root_node:
        return
    inOrderTraversal(root_node.leftChild)
    print(root_node.data)
    inOrderTraversal(root_node.rightChild)

#Initializing the Binary Tree
newTree = TreeNode("Drinks")
leftChild = TreeNode("Hot")
tea = TreeNode("Latte")
coffee = TreeNode("Mocha")
leftChild.leftChild = tea
leftChild.rightChild = coffee

rightChild = TreeNode("Cold")
coke = TreeNode("Coke")
sprite = TreeNode("Sprite")
rightChild.leftChild = coke
rightChild.rightChild = sprite

newTree.leftChild = leftChild
newTree.rightChild = rightChild

inOrderTraversal(newTree)

Output

Time and space Complexity

The time complexity for InOrder traversal is O(N) because the function recursively visits all nodes of the tree. The space complexity for InOrder traversal is O(N) because the stack holds memory continuously while using a recursive function.

PostOrder Traversal in Binary Tree

Post-order traversal means visiting the left branch, then the current node, and finally, the right branch. In a post-order traversal, the root is always the last node visited.

Example:

PostOrder Traversal – N8 -> N9 -> N4 -> N5 -> N2 -> N6 -> N7 -> N3 -> N1

Implementation of PostOrder Traversal

For implementing in-order traversal in a binary tree, the below code makes use of a recursive function postOrderTraversal. Initially, the root node is passed as an argument to this function.

If the root node is not empty, a recursive call to the left child is made, followed by a recursive call to the right child, and then a displaying the content of the current node. The function postOrderTraversal terminates a recursion when the encountered node is found to be empty.

#Creating the PostOrder Function
def postOrderTraversal(root_node):
    if not root_node:
        return
    postOrderTraversal(root_node.leftChild)
    postOrderTraversal(root_node.rightChild)
    print(root_node.data)

#Initializing the Binary Tree
newTree = TreeNode("Drinks")
leftChild = TreeNode("Hot")
tea = TreeNode("Latte")
coffee = TreeNode("Mocha")
leftChild.leftChild = tea
leftChild.rightChild = coffee

rightChild = TreeNode("Cold")
coke = TreeNode("Coke")
sprite = TreeNode("Sprite")
rightChild.leftChild = coke
rightChild.rightChild = sprite

newTree.leftChild = leftChild
newTree.rightChild = rightChild

postOrderTraversal(newTree)

Output

Time and space Complexity

The time complexity for PostOrder traversal is O(N) because the function recursively visits all nodes of the tree. The space complexity for PostOrder traversal is O(N) because the stack holds memory continuously while using a recursive function.

Level Order Traversal in Binary Tree

Trees can also be traversed in a level order manner. The Level Order traversal is a breadth-first traversal where nodes are visited level-by-level. Then, they are traversed in a left-to-right manner.

Example:

Level Order Traversal – N1 -> N2 -> N3 -> N4 -> N5 -> N6 -> N7 -> N8 -> N9

Implementation of Level Order Traversal

For implementing level-order traversal in a binary tree, the below code makes use of a queue to implement the same. The function levelOrderTraversal is initially called with the root node as its parameter.

If the current node is not empty, the same is pushed into a queue, followed by iterating the queue. Queue iteration works as follows:

• The first element is dequeued and its content is displayed.
• The children of this node are enqueued into the same queue.
• The same procedure is implemented for all nodes that enter the queue.
• The function terminates when every element is dequeued.

#Creating the Level Order Function
def levelOrderTraversal(root_node):
    if not root_node:
        return
    else:
        tempQueue = queue.Queue()
        tempQueue.enqueue(root_node)
        while not(tempQueue.isEmpty()):
            root = tempQueue.dequeue()
            print(root.value.data)
            if (root.value.leftChild is not None):
                tempQueue.enqueue(root.value.leftChild)

            if (root.value.rightChild is not None):
                tempQueue.enqueue(root.value.rightChild)

#Initializing the Binary Tree
newTree = TreeNode("Drinks")
leftChild = TreeNode("Hot")
tea = TreeNode("Latte")
coffee = TreeNode("Mocha")
leftChild.leftChild = tea
leftChild.rightChild = coffee

rightChild = TreeNode("Cold")
coke = TreeNode("Coke")
sprite = TreeNode("Sprite")
rightChild.leftChild = coke
rightChild.rightChild = sprite

newTree.leftChild = leftChild
newTree.rightChild = rightChild

levelOrderTraversal(newTree)

Output

Time and space Complexity

The time complexity for Level Order traversal is O(N) because the function visits all nodes of the tree. The space complexity for Level Order traversal is O(N) because we store the data of the tree in a temporary queue.

Searching for a node in Binary Tree

Searching for a node in a Binary Tree can be performed using the knowledge of Level Order Traversal. While we perform level order traversal and visit every node, we can compare the value of that node with the value to be searched.

Example:

We search every node of the tree level-by-level. If the node is found, we return a message “Element Found”.

Implementation of Search in Binary Tree

To perform a search in a binary tree, we define a function searchBT which initially takes two arguments – the root node and the value to be searched. Within this function, we perform a level order traversal to visit every node of the tree.

We compare each node’s value with the searched value. If the required node is found, we return a message indicating success. Otherwise, the search continues. If the element is not found, we return a message likewise.

#Searching a node in a Binary Tree
def searchBT(root_node, node_value):
    if not root_node:
        return "The Binary Tree does not exist."
    else:
        tempQueue = queue.Queue()
        tempQueue.enqueue(root_node)
        while not(tempQueue.isEmpty()):
            root = tempQueue.dequeue()
            if root.value.data == node_value:
                return "Element Found"
            if (root.value.leftChild is not None):
                tempQueue.enqueue(root.value.leftChild)

            if (root.value.rightChild is not None):
                tempQueue.enqueue(root.value.rightChild)
        return "Element Not Found"

#Initializing the Binary Tree
newTree = TreeNode("Drinks")
leftChild = TreeNode("Hot")
tea = TreeNode("Latte")
coffee = TreeNode("Mocha")
leftChild.leftChild = tea
leftChild.rightChild = coffee

rightChild = TreeNode("Cold")
coke = TreeNode("Coke")
sprite = TreeNode("Sprite")
rightChild.leftChild = coke
rightChild.rightChild = sprite

newTree.leftChild = leftChild
newTree.rightChild = rightChild

print(searchBT(newTree, "Latte"))

#Output
Element Found

Time and space Complexity

The time complexity for searching in a binary tree is O(N) because the function visits all nodes and compares each one with the value to be searched. The space complexity for searching is O(N) because we store the data of the tree in a temporary queue.

Insertion of a node in Binary Tree

Insertion in a Binary Tree can be implemented with the use of a temporary queue. We store all the elements of the tree in this temporary queue one by one till we reach the leaf nodes. Then, we figure out the apt space for the node to be inserted and place it as a new leaf node of the tree.

Example:

Implementation of Insertion in Binary Tree

Insertion in a binary tree is performed by creating a queue to store the value of data elements. The root node is placed at index 1 of this queue. Then, we subsequently keep inserting elements by using the enqueue function.

If any parent node is at index i in the queue, then by convention, its left child will be placed at index 2i and the right child will be placed at index 2i+1.

#Inserting a node in a Binary Tree
def insertNodeBT(root_node, new_node):
    if not root_node:
        root_node = new_node
    else:
        tempQueue = queue.Queue()
        tempQueue.enqueue(root_node)
        while not(tempQueue.isEmpty()):
            root = tempQueue.dequeue()
            if root.value.leftChild is not None:
                tempQueue.enqueue(root.value.leftChild)
            else:
                root.value.leftChild = new_node
                return "The node has been successfully inserted."
            if root.value.rightChild is not None:
                tempQueue.enqueue(root.value.rightChild)
            else:
                root.value.rightChild = new_node
                return "The node has been successfully inserted."

#Initializing the Binary Tree
newTree = TreeNode("Drinks")
leftChild = TreeNode("Hot")
tea = TreeNode("Latte")
coffee = TreeNode("Mocha")

leftChild.leftChild = tea
leftChild.rightChild = coffee
rightChild = TreeNode("Cold")
coke = TreeNode("Coke")
rightChild.leftChild = coke

newTree.leftChild = leftChild
newTree.rightChild = rightChild
sprite = TreeNode("Sprite")
print(insertNodeBT(newTree, sprite))

#Output
The node has been successfully inserted.

Time and space Complexity

The time complexity for insertion in a binary tree is O(N) because the function visits all nodes and finds out the apt place for inserting the new element. The space complexity for insertion is O(N) because we store the data of the tree in a temporary queue.

Deletion of a node from Binary Tree

The deletion of a node from a binary tree is a sequential process. If we wish to delete an internal node from the tree, we must replace it with another node so that the connected nodes are not disturbed.

Thus, we replace the deleted node with the deepest node in the tree. The deepest node in a tree is the last node that is encountered while performing a Level Order traversal.

After Deletion:

Implementation of Deletion of Node from Binary Tree

• The getDeepestNode iterates through the tree and returns the deepest node of the tree. It uses a temporary queue and enqueue values into it. Then, we subsequently dequeue elements until we are left with the deepest node of the tree and return that node.
• The deleteDeepestNode function traverses to the deepest node and removes it from the tree.
• The deleteNodeBT function gets the value of the deepest node and assigns it to the node to be deleted. Further, it deletes the deepest node of the tree.

#Deleting a node in a Binary Tree
#Function to return the deepest node in the tree
def getDeepestNode(root_node):
    if not root_node:
        return
    else:
        tempQueue = queue.Queue()
        tempQueue.enqueue(root_node)
        while not(tempQueue.isEmpty()):
            root = tempQueue.dequeue()
            if (root.value.leftChild is not None):
                tempQueue.enqueue(root.value.leftChild)

            if (root.value.rightChild is not None):
                tempQueue.enqueue(root.value.rightChild)
        deepestNode = root.value
        return deepestNode

#Function to delete the deepest node from the tree
def deleteDeepestNode(root_node, dNode):
    if not root_node:
        return
    else:
        tempQueue = queue.Queue()
        tempQueue.enqueue(root_node)
        while not(tempQueue.isEmpty()):
            root = tempQueue.dequeue()
            if root.value is dNode:
                root.value = None
                return
            if root.value.rightChild:
                if root.value.rightChild is dNode:
                    root.value.rightChild = None
                    return
                else:
                    tempQueue.enqueue(root.value.rightChild)
            if root.value.leftChild:
                if root.value.leftChild is dNode:
                    root.value.leftChild = None
                    return
                else:
                    tempQueue.enqueue(root.value.leftChild)

#Delete function which replaces the deleted node with the deepest node
def deleteNodeBT(root_node, node):
    if not root_node:
        return "The Binary Tree does not exist."
    else:
        tempQueue = queue.Queue()
        tempQueue.enqueue(root_node)
        while not(tempQueue.isEmpty()):
            root = tempQueue.dequeue()
            if root.value.data == node:
                dNode = getDeepestNode(root_node)
                root.value.data = dNode.data
                deleteDeepestNode(root_node, dNode)
                return "The node has been successfully deleted."
            if (root.value.leftChild is not None):
                tempQueue.enqueue(root.value.leftChild)

            if (root.value.rightChild is not None):
                tempQueue.enqueue(root.value.rightChild)
        return "The node could not be deleted."

#Initializing the Binary Tree
newTree = TreeNode("Drinks")
leftChild = TreeNode("Hot")
tea = TreeNode("Latte")
coffee = TreeNode("Mocha")
leftChild.leftChild = tea
leftChild.rightChild = coffee

rightChild = TreeNode("Cold")
coke = TreeNode("Coke")
sprite = TreeNode("Sprite")
rightChild.leftChild = coke
rightChild.rightChild = sprite

newTree.leftChild = leftChild
newTree.rightChild = rightChild

print(deleteNodeBT(newTree, "Cold"))
levelOrderTraversal(newTree)

Output

Time and space Complexity

The time complexity for deletion in a binary tree is O(N) because the function iterates over all the nodes of the tree. The space complexity for insertion is O(N) because we store the data of the tree in a temporary queue.

Deletion of Entire Binary Tree

For the deletion of an entire binary tree, all we need to do is set the root node of the tree to None. Then, we free up the memory space by setting the left and the right child nodes of the root to None as well.

Implementation of Deletion of Entire Binary Tree

To delete an entire binary tree, we remove the data from the root node and set the left and right child references to None, thereby freeing up the allocated memory space.

#Deleting Entire Binary Tree
def deleteBT(root_node):
    root_node.data = None
    root_node.leftChild = None
    root_node.rightChild = None
    return "The BT has been successfully deleted"

#Initializing the Binary Tree
newTree = TreeNode("Drinks")
leftChild = TreeNode("Hot")
tea = TreeNode("Latte")
coffee = TreeNode("Mocha")
leftChild.leftChild = tea
leftChild.rightChild = coffee

rightChild = TreeNode("Cold")
coke = TreeNode("Coke")
sprite = TreeNode("Sprite")
rightChild.leftChild = coke
rightChild.rightChild = sprite

newTree.leftChild = leftChild
newTree.rightChild = rightChild

print(deleteBT(newTree))

#Output
The BT has been successfully deleted

Time and Space Complexity

The time complexity for deletion of an entire binary tree is O(1) because it takes constant time for setting the references to None. The space complexity for deleting the binary tree is O(1) as well because no additional memory is required.

Creation of Binary Tree built using List

In python, a Binary tree can be implemented with the use of the list data structure as well. To initialize a binary tree using a list, we first create an empty list to store the nodes of the tree. The first node of the tree is left empty for better mathematical calculations.

The root node of the tree is placed at index 1 of the list. The left child of the x^th node of the tree is placed at index 2x of the list and the right child is placed at the index 2x+1.

To initialize the binary tree using a python list, we create a BinaryTree class. The object of this class takes the size of the list as one of its parameters. Then, we initialize an empty list of the designated size. We then initialize a variable lastIndexUsed and set it to 0. This variable is for determining which cell was used in the previous function call.

#Creating the Binary Tree Class
class BinaryTree:
    def __init__(self, size):
        self.treeList = size * [None]
        self.lastIndexUsed = 0
        self.maxSize = size

newBT = BinaryTree(8)

Time and space Complexity

The time complexity for the creation of a binary tree using a list is O(1) as it takes constant time to initialize data items for the class. The space complexity is O(N) because we create a list data structure with the same size as the size of our tree.

Operations on Binary Tree built using List

Insertion of a node in Binary Tree

In the case of a binary tree created using a list, we can encounter a case where the maximum size of the binary tree has been reached. Thus, we simply return an error message if the binary tree is already fully occupied.

If there is a vacant space in the list, we use level order traversal and locate the place where our new node can be added in the binary tree. Once we find the spot where the new node is to be connected, we can simply input it into our list at the required index value.

Example:

Implementation of Insertion in Binary Tree

The insertNode function first checks whether or not the max occupancy of the binary tree has been reached. If not, the function simply inserts the value in the next empty space in the list.

#Inserting a node in a Binary Tree
def insertNode(self, value):
        if self.lastIndexUsed + 1 == self.maxSize:
            return "The Binary Tree is fully occupied."
        self.treeList[self.lastIndexUsed+1] = value
        self.lastIndexUsed += 1
        return "The value has been successfully inserted."

#Initializing the Binary Tree
newTree = BinaryTree(8)
newTree.insertNode("Drinks")
newTree.insertNode("Hot")
newTree.insertNode("Cold")
newTree.insertNode("Latte")

newTree.insertNode("Mocha")

#Output
The value has been successfully inserted.

Time and space Complexity

The time complexity for insertion in a binary tree is O(1) because it takes constant time to search for a vacant place and input the required value. The space complexity is O(1) as well since no additional memory is required for insertion.

Searching for a node in Binary Tree

Searching for a node in a Binary Tree can be performed using the knowledge of Level Order Traversal. While we perform level order traversal and visit every node, we can compare the value of that node with the value to be searched.

Example:

We search every node of the tree level-by-level. If the node is found, we return a message “Element Found”.

Implementation of Search in Binary Tree

We use the for loop to iterate over the list and compare the value of each node to the value to be searched. If the value is found we return the “Element Found” message in the searchNode function.

#Searching a node in a Binary Tree
def searchNode(self, nodeValue):
        for i in range(len(self.treeList)):
            if self.treeList[i] == nodeValue:
                return "Element Found."
        return "Element Not Found."

#Initializing the Binary Tree
newTree = BinaryTree(8)
newTree.insertNode("Drinks")
newTree.insertNode("Hot")
newTree.insertNode("Cold")
newTree.insertNode("Latte")
newTree.insertNode("Mocha")

print(newTree.searchNode("Latte"))

#Output
Element Found.

Time and space Complexity

The time complexity for searching in a binary tree is O(N) because the function iterates over all nodes and compares each one with the value to be searched. The space complexity for searching is O(1) because no additional memory is required.

PreOrder Traversal in Binary Tree

Example:

PreOrder Traversal – N1 -> N2 -> N4 -> N8 -> N9 -> N5 -> N3 -> N6 -> N7

Implementation of PreOrder Traversal

The preOrderTraversal function displays the root node and then performs recursion over its left child node, and then the right child node. This process is repeated subsequently for all the nodes.

#Creating the PreOrder Function
def preOrderTraversal(self, index):
        if index > self.lastIndexUsed:
            return
        print(self.treeList[index])
        self.preOrderTraversal(index*2)
        self.preOrderTraversal(index*2 + 1)

#Initializing the Binary Tree
newTree = BinaryTree(8)
newTree.insertNode("Drinks")
newTree.insertNode("Hot")
newTree.insertNode("Cold")
newTree.insertNode("Latte")
newTree.insertNode("Mocha")

newTree.preOrderTraversal(1)

Output

Time and space Complexity

The time complexity for PreOrder traversal is O(N) because the function recursively visits all nodes of the tree. When we use a recursive function, it holds up memory in the stack so as to recognize its next call. Thus, the space complexity for PreOrder traversal is O(N).

InOrder Traversal in Binary Tree

Example:

InOrder Traversal – N8 -> N4 -> N9 -> N2 -> N5 -> N1 -> N6 -> N3 -> N7

Implementation of InOrder Traversal

The inOrderTraversal function performs recursion over the left child of the root node, displays the root node, and then performs recursion on the right child node. This process is repeated subsequently for all the nodes.

#Creating the InOrder Function
def inOrderTraversal(self, index):
        if index > self.lastIndexUsed:
            return
        self.inOrderTraversal(index*2)
        print(self.treeList[index])
        self.inOrderTraversal(index*2+1)

#Initializing the Binary Tree
newTree = BinaryTree(8)
newTree.insertNode("Drinks")
newTree.insertNode("Hot")
newTree.insertNode("Cold")
newTree.insertNode("Latte")
newTree.insertNode("Mocha")

newTree.inOrderTraversal(1)

Output

Time and space Complexity

The time complexity for InOrder traversal is O(N) because the function recursively visits all nodes of the tree. The space complexity for InOrder traversal is O(N) as well because the stack holds memory continuously while using a recursive function.

PostOrder Traversal in Binary Tree

Example:

PostOrder Traversal – N8 -> N9 -> N4 -> N5 -> N2 -> N6 -> N7 -> N3 -> N1

Implementation of PostOrder Traversal

The postOrderTraversal function performs recursion over the left child of the root node, then on the right child node, and further displays the value of the root node. This process is repeated subsequently for all the nodes.

#Creating the PostOrder Function
def postOrderTraversal(self, index):
        if index > self.lastIndexUsed:
            return
        self.postOrderTraversal(index*2)
        self.postOrderTraversal(index*2+1)
        print(self.treeList[index])

#Initializing the Binary Tree
newTree = BinaryTree(8)
newTree.insertNode("Drinks")
newTree.insertNode("Hot")
newTree.insertNode("Cold")
newTree.insertNode("Latte")
newTree.insertNode("Mocha")

newTree.postOrderTraversal(1)

Output

Time and space Complexity

The time complexity for PostOrder traversal is O(N) because the function recursively visits all nodes of the tree. The space complexity for PostOrder traversal is O(N) because the stack holds memory continuously while using a recursive function.

Level Order Traversal in Binary Tree

In the case of level order traversal, we traverse the tree level-by-level. Since we input the elements in the list according to the level order traversal, we simply iterate over the list and print each element.

Example:

Level Order Traversal – N1 -> N2 -> N3 -> N4 -> N5 -> N6 -> N7 -> N8 -> N9

Implementation of Level Order Traversal

The levelOrderTraversal function simply iterates over the list and prints each element in the order they are stored.

#Creating the Level Order Function
def levelOrderTraversal(self, index):
        for i in range(index, self.lastIndexUsed + 1):
            print(self.treeList[i])

#Initializing the Binary Tree
newTree = BinaryTree(8)
newTree.insertNode("Drinks")
newTree.insertNode("Hot")
newTree.insertNode("Cold")
newTree.insertNode("Latte")
newTree.insertNode("Mocha")

newTree.levelOrderTraversal(1)

Output

Time and space Complexity

The time complexity for Level Order traversal is O(N) because the function visits all nodes of the tree using a for loop function. The space complexity for Level Order traversal is O(1) because no additional memory is required.

Deletion of a node from Binary Tree

The deletion of a node from a binary tree is a sequential process. If we wish to delete an internal node from the tree, we must replace it with another node so that the connected nodes are not disturbed. Thus, we replace it with the last node of the tree, i.e., the node at the index lastIndexUsed.

After Deletion:

Implementation of Deletion of Node from Binary Tree

The deleteNode function replaces the node to be deleted by the last element in the list. Then it decreases the size of the list by 1, eliminating the last element.

#Deleting a node in a Binary Tree
def deleteNode(self, value):
        if self.lastIndexUsed == 0:
            return "There is not any node to delete"
        for i in range(1, self.lastIndexUsed+1):
            if self.treeList[i] == value:
                self.treeList[i] = self.treeList[self.lastIndexUsed]
                self.treeList[self.lastIndexUsed] = None
                self.lastIndexUsed -= 1
                return "The node has been successfully deleted"

#Initializing the Binary Tree
newTree = BinaryTree(8)
newTree.insertNode("Drinks")
newTree.insertNode("Hot")
newTree.insertNode("Cold")
newTree.insertNode("Latte")
newTree.insertNode("Mocha")

print(newTree.deleteNode("Cold"))
newTree.levelOrderTraversal(1)

Output

Time and space Complexity

The time complexity for deletion in a binary tree is O(N) because the function iterates over all the nodes of the tree. The space complexity for insertion is O(1) because no additional memory is required.

Deletion of Entire Binary Tree

To delete an entire binary tree built using a list, we simply set the designated list to None and free up the memory space.

Implementation of Deletion of Entire Binary Tree

To delete an entire binary tree, we simply set the list to None, freeing up the space allocated by it.

#Deleting Entire Binary Tree
def deleteBT(self):
        self.treeList = None
        return "The BT has been successfully deleted"

#Initializing the Binary Tree
newTree = BinaryTree(8)
newTree.insertNode("Drinks")
newTree.insertNode("Hot")
newTree.insertNode("Cold")
newTree.insertNode("Latte")
newTree.insertNode("Mocha")

print(newTree.deleteBT())

#Output
The BT has been successfully deleted

Time and Space Complexity

The time complexity for deletion of an entire binary tree is O(1) because it takes constant time for setting the references to None. The space complexity for deleting the binary tree is O(1) as well because no additional memory is required.

Binary Tree using Linked List vs Binary Tree using List