Introduction to Trees

Trees

Tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes.

There various types of trees:
-Binary Tree: A tree in which each node has at most 2 children nodes.
-Ternary Tree: A tree in which each node has at most 3 children nodes.
-N-ary Tree: A tree in which each node has at most N children nodes.

In this post, we will be covering Binary Search Trees and the method to insert values, In-order traversal as well as delete a node.

What is a Binary Search Tree?

A binary search tree is a hierarchical data structure where each node has at most two children, with values ordered such that left child values are smaller and right child values are greater.

A Binary Search Tree can be visualized by the following image:

Creating a Binary Search Tree

Before creating the Binary Search Tree, we first need to define the Node class. As mentioned in the previous posts, a Node contains data which is the value to be stored, and two pointers. Here one pointer called as left is used to point to the left child and the other called right is used to point to the right child. We specify the left and right as None as when we add a node it doesn't have children yet.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

Now we have created the class Node, we can now proceed in working with the BinarySearchTree class. In the tree class, we will modify the constructor or __init__(self) to automatically create the root node.

class BinarySearchTree:
    def __init__(self):
        self.root = Node(None)

Now in this class we will specify methods to insert a node, in this method we accept a key or value to be inserted. We will then create a node. Now we first check if we have a root node , if we do not, ie, root is None then we make this newly created node as the root. Otherwise, we iterate from the root node and compare the input data value to the key. If it's greater than the key, we move to the left child, if it's lesser, we move to the right child and if we come to the leaf node, depending on the comparison, we will add this node as the left or right child respectively.

def insert(self, key):
    node = Node(key)
    if self.root is None:
       self.root = node
       return
    prev = None
    temp = self.root
    while temp is not None:
          if temp.data > key:
             prev = temp
             temp = temp.left
          elif temp.data < key:
             prev = temp
             temp = temp.right
     if prev.data > key:
        prev.left = node
     else:
        prev.right = node

Traversal

In this process, we move through the Binary Search Tree in a specific way. There various Traversal Methods are:
-In-order: In which for each node in the tree, we first visit the left child, then the node and then it's right child.
-Pre-order: In which for each node in the tree, we first visit the node, then the node's left child and then it's right child.
-Post-order: In which for each node in the tree, we first visit the node's left child and then it's right child and then the node itself.

In-order traversal

In, in-order traversal , we essentially first recursively iterate through the left sub-tree and once we reach the leaf, since the node has no left child, the data of the node is printed, and since the node does not have right child, we go back to the previous call (which called on the left sub-tree) and then we print that node's data and then call it's right sub-tree. The logic applies the same and this repeats till we reach the right most node of the tree.

def inorder(self, node):
    if node is not None:
       self.inorder(node.left)
       print(str(node.data) + " ", end="") #to print on same line
       self.inorder(node.right)

Delete

So when we delete a node, we first find the node which contains the key or the data to be deleted by recursively calling the left/right sub-tree based if the key is lower/higher than the current node respectively. When the key matches the node data , if the node does not hava a left child, we iterate it's right child, and if does not have a right child, we iterate it's left child and if has both, we find the minimum of the right sub-tree so that we can replace the node's data with the minimum data, resulting in a duplicate, and we recursively call the function, with the node to be deleted as the root, and it's data as the key. Till it reaches a leaf node and as a result returns None. Indicating the node is deleted.

def deleteNode(self, root, key):
        if root is None:
            return root

        if key < root.data:
            root.left = self.deleteNode(root.left, key)
        elif key > root.data:
            root.right = self.deleteNode(root.right, key)
        else:
            if root.left is None:
                return root.right
            elif root.right is None:
                return root.left
            root.data = self.minValue(root.right)
            root.right = self.deleteNode(root.right, root.data)
        return root

    def minValue(self, node):
        current = node
        while current.left is not None:
            current = current.left
        return current.data

The full code to implement the Binary Search Tree is provided below.

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        node = Node(key)
        if self.root is None:
            self.root = node
            return
        prev = None
        temp = self.root
        while temp is not None:
            if temp.data > key:
                prev = temp
                temp = temp.left
            elif temp.data < key:
                prev = temp
                temp = temp.right
        if prev.data > key:
            prev.left = node
        else:
            prev.right = node

    def inorder(self, node):
        if node is not None:
            self.inorder(node.left)
            print(str(node.data) + " ", end="")
            self.inorder(node.right)

    def deleteNode(self, root, key):
        if root is None:
            return root

        if key < root.data:
            root.left = self.deleteNode(root.left, key)
        elif key > root.data:
            root.right = self.deleteNode(root.right, key)
        else:
            if root.left is None:
                return root.right
            elif root.right is None:
                return root.left
            root.data = self.minValue(root.right)
            root.right = self.deleteNode(root.right, root.data)
        return root

    def minValue(self, node):
        current = node
        while current.left is not None:
            current = current.left
        return current.data

bst = BinarySearchTree()
while True:
    print("\nBinary Search Tree Menu:")
    print("1. Insert")
    print("2. Display All Values")
    print("3. Delete")
    print("4. Exit")

    choice = input("Enter choice: ")

    if choice == '1':
        data = int(input("Enter data: "))
        bst.insert(data)
        print(f"{data} has been inserted.")
    elif choice == '2':
        bst.inorder(bst.root)
    elif choice == '3':
        data = int(input("Enter the data: "))
        bst.root = bst.deleteNode(bst.root, data)
        print(f"{data} has been deleted.")
    elif choice == '4':
        break
    else:
        print("Invalid choice")