Introduction to Trees
Tags: datastructures, python
Published: 2024-05-02 14:01:08

## 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:

![Binary Search Tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9xltesljtxffz5t4lcvu.png)


### 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. 

```py
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. 

```py
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. 

```py
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. 

```py
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. 

```py
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.

```py
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")
```

### NOTE:
If you're finding it a bit hard to visualize how the Binary Search Tree works, [here](https://www.cs.usfca.edu/~galles/visualization/BST.html) is a very helpful website that does it for you.