Application of Tree Data Structures

4 min readApr 21, 2022

What is Tree Data Structure?

We all know what a tree looks like. It has roots, stems, branches, and leaves. Each leaf of a tree can be traced to its root via a unique path. This hierarchical structure of trees is used in Computer science as an abstract data type for various applications like data storage, and search and sort algorithms. In definition,

A tree is a nonlinear hierarchical data structure that consists of nodes connected by edges.

What does it look like?

The tree has one node called a root. The tree originates from this, and hence it does not have any parent.
Each node has one parent only but can have multiple children.
Each node is connected to its children via edge.

Why Tree Data Structure?

Other data structures such as arrays, linked list, stack, and queue are linear data structures that store data sequentially. In order to perform any operation in a linear data structure, the time complexity increases with the data size. But it is not acceptable in today’s computational world.

Let’s take our computer file system as an example. Every folder has its own name, and we normally store any related files in those folders. When you are looking for any specific file or folder, you can search from the most parent folder and start digging deeper or you can simply type the file name in the search bar and find it. So basically our computer does it all for us from the top level of the root folder and gives us back the result.

File System (https://networkencyclopedia.com/wp-content/uploads/2019/10/file-system.jpg)

Types of Tree Data Structures

Now that we know about the basics of a Tree, let’s talk about the types of trees you will come across in Data Structures. There are many different types of tree data structures available and they all have their specific usage, but we will talk about the five most common data structures.

1. General Tree

This type of tree is free of all constraints. The word Constraints here mean, how we insert and delete the nodes based on the values of the nodes. There are no limits on the number of nodes that could be created and linked to one another.

2. Binary Tree

A binary tree is a tree data structure in which each parent node can have a most two children. Each node of a binary tree consisted of three items:

Data item
Address of a left child
Address of a right child

3. Binary Search Tree

A binary search tree is a data structure that quickly allows us to maintain a sorted list of numbers. It’s called a binary search tree because each tree node has a maximum of two children and it can be used to search for the presence of a number in 0(log(n)) time.

Properties of Binary search tree:

All nodes of the left subtree are less than the root node.
All nodes of the right subtree are more than the root node.
Both subtrees of each node are also BSTs.

4. AVL Tree

AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0, or +1. AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis.

The balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of the right subtree of that node.
The self-balancing property of the AVL tree is maintained by the balance.

5. Red-Black Tree

The red-Black tree is a self-balancing binary search tree in which each node contains an extra bit for denoting the color of the node, either red or black.

Properties of Red-Black tree:

Red-Black: Every node is colored either red or black.
Root: The root is black.
Leaf: Every leaf(NIL) is black.
Red: If a red node has children then, the children are always black.
Depth: For each node, any simple path from this node to any of its descendant leaf has the same black depth.

Conclusion

These are the trees in data structures that programmers use to design the flow of data. Understanding their distinct characteristics and applications is important. I would recommend digging deeper into different types of data structures as there are many more types available. It will help when you take a look at real-life examples of data structures.