## What are the operations implemented in a tree and what are its applications?

We have studied what are trees and how to traverse them. But is that enough? Since it is such a strong data structure, it must have a good utility which means various operations could be performed on it.

But what kind of operations? **Insertion**, **deletion **and **searching **of elements are among the most basic operations that most data structures support.

But there are several other operations that can be performed on trees like →

- Finding the maximum and the minimum element in the tree
- Finding the sum of all elements in the tree

Let us now dive deep in and see how each of these is implemented in trees. For the purposes of this blog, we will just consider binary trees during implementation for simplicity. Also, our primary mode of implementation for the tree here will be using linked representation.

#### 1. Insertion

Insertion in a tree can be performed in various ways depending on where you need to insert the new element. We can →

- Insert the new element at the rightmost or leftmost vacant position we find.
- Randomly insert the element in the first position we find vacant while we traverse a tree.
*The type of traversal(preorder, postorder, inorder, level order) chosen here***may**change the final structure of the tree. - Make the new element
**root**of the binary tree with the previous root as now its right child and the*left child of the previous root*will now become the left child of this new root.

The possibilities are endless…

- There are many other ways we can find to insert an element in the tree. Comment down below more ways that you can insert an element in a binary tree.

Among these three, the first method is relatively most difficult to implement so let's try to implement that.

Solution Steps

We first need to select the type of traversal that we shall perform on the tree to determine the vacant place. Let us do this with **inorder traversal**. Parameters: **root, new_node**

- Check if the root itself is null or not, i.e., if it is an empty tree or not.
- In the case of an empty tree, just return the
**new_node**as root. - Begin traversing the tree in inorder fashion →

- Check if left child exists or not, if it doesn’t, make the left child as
**new_node**and exit, else proceed inorder with the left child. - Check if right child exists or not, if it doesn’t, make the right child as
**new_node**and exit, else proceed inorder with the right child.

4. This way, whenever we get an empty spot, we insert the **new_node **and break the process that instant.

Pseudo-Code

```
TreeNode insert_node_inorder(TreeNode root, TreeNode new_node)
{
if ( root == NULL )
return new_node
if ( root.left == NULL )
root.left = new_node
else
root.left = insert_node_inorder(root.left, new_node)
```

```
if ( root.right == NULL )
root.right = new_node
else
root.right = insert_node_inorder(root.right, new_node)
return root
}
```

**2. Searching**

Searching an element in a simple binary tree is quite simple actually. We just check if the current node’s value matches with the given value or not and then recurse to the left and right subtrees repeating the same process.

Pseudo-Code

```
bool search(TreeNode root, int item)
{
if ( root == NULL )
return 0
if ( root.val == item )
return 1
if ( search(root.left, item) == 1 )
return 1
else if ( search(root.right, item) == 1 )
return 1
else
return 0
}
```

**3. Deletion**

Deletion of a node in a tree may get a little tricky when you think about what to do with the left child and the right child of that node. We need to follow a certain convention in this process, whatever the programmer sees fit.

To keep it simple, we shall just replace the deleted node with a leaf node. But which leaf node? → Well, you can choose this as you wish too. A simple choice is to find the leftmost or rightmost node of the subtree with the node to be deleted as root.

Although, if the node to be deleted is itself a leaf node, we won’t need to replace it with any node, or if it has only one child, we can use replace the node with its child.

Solution Steps

Our purpose is to accept the root of tree and value **item** and return the root of the modified tree after deleting the node with value **item.**

- Check if the root is NULL, if it is, just return the root itself.
- Search for an
**item**in left and right subtree and recurse to them if found. - If the
**item**is not found in the left and right subtree, either the value is not in the tree or**root.val == item**. - We now need to delete the root of the tree. There are three cases possible for this.
**CASE 1: No Child →**Just delete**root**or deallocate space occupied by it**CASE 2: One Child**→Replace**root**by its child**CASE 3: Two Children**

- Find the leftmost node in the left subtree of
**root.**Let us call it**new_root.** - Replace
**root**by**new_root**. - Now recurse to the left subtree and delete
**new_root.**

8. Return the **root**.*This is a basic approach and hence searches node by value. It is assumed that all values in the node are unique. Also, keep in mind that a basic binary tree has no rules like Binary Search Tree for the ordering of elements so you can change the convention as per your need.*

Pseudo-Code

```
TreeNode delete_element(TreeNode root, int item)
{
if ( root == NULL )
return root
if ( search(root.left, item) == True )
root.left = delete_element(root.left, item)
else if ( search(root.right, item) == True )
root.right = delete_element(root.right, item)
else if ( root.val == item )
{
// No child exists
if ( root.left == NULL and root.right == NULL )
delete root
// Only one child exists
else if ( root.left == NULL or root.right == NULL )
{
if ( root.left == NULL )
return root.right
else
return root.left
}
// Both left and right child exists
else
{
TreeNode selected_node = root
while ( selected_node.left != NULL )
selected_node = selected_node.left
root.val = selected_node.val
root.left = delete_element(root.left, selected_node.val)
}
}
return root
}
```

#### 4. Finding minimum and maximum

Finding minimum and maximum in a tree can be done via a traversal too. For example, we can just do an inorder traversal of the tree and update the values of **min_val** and **max_val **as we traverse the tree.

Let us understand this by a code

```
void getMinMax(TreeNode root, int& min_val, int& max_val)
{
if ( root == NULL )
return
getMinMax(root.left, min_val, max_val)
```

```
min_val = min(min_val, root.val)
max_val = max(max_val, root.val)
```

```
getMinMax(root.right, min_val, max_val)
}
```

→ Here, **min_val **and **max_val** are passed by reference and not by value.

#### 5. Sum of all nodes

This is another operation that can be performed based on traversal only. Can you try this now based on your understanding from the above codes?

Maybe you will write the code something like this →

```
void getSum(TreeNode root, int& sum)
{
if ( root == NULL )
return
getSum(root.left, sum)
sum += root.val
getSum(root.right, sum)
}
```

Although, in this case, the code can also be written in this manner

```
int getSum(TreeNode root)
{
if ( root == NULL )
return NULL
int left_sum = getSum(root.left)
int right_sum = getSum(root.right)
```

```
return left_sum + root.val + right_sum
}
```

Both codes are correct and equally efficient. It depends on the programmer to right either one.

#### Applications of Tree data structure

**A Tree** is a very useful data structure with a lot of applications and is used internally in many technologies around you →

- Chatting with someone or googling something? Using autocomplete? Based on
**Tries**, a tree. - Using webpages? Transferring data?
**HTML/XML Parsers**are based on tree data structure as well. - So many
**networking models**that we use couldn’t be implemented without trees - You can already guess some of its various uses in
**social networking.**

And these are just a few examples of how much **tree data structure** is used in our daily lives.

Let us list out a few special types of trees with their specific purposes →

**Binary Search Tree(BST)**offers fast insert, search and delete operations on data- Indexing on a database is done using
**B+trees, B- trees and T-Trees** **Tries:**Stores strings in tree format decreasing search time**Heap:**A variation of tree implemented using arrays, used to built priority queues- Pattern Searching in a fixed text is implemented using
**Suffix Trees** **K-D Tree**(K-dimensional) is used to organize points in K-dimensional space