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
