We are already aware of data structures like an array, linked list, stack, queue, etc. But can you guess what is common between all the above data structures ..and why we introduce tree in data structure?
Yes, you guessed it right. All the data structures are LINEAR data structures. Why is it called linear..? Because you traverse it one after another and only one element can be directly accessed while traversing.
But there are many real-life things which we can’t represent linearly or I would say that we can represent them linearly but it will bear you the high cost.
Let us discuss some of the examples,
Computer Hard Drives
We almost use computers or laptops every day. When we go to my computer section, we see that there are four sections of our hard drives. C drive, E drive, F drive, and H drive.
Now let think of a situation,
Let consider the structure of a hard drive like shown in the picture,
Let’s say we want to access a file in Drive F.
While traversing linearly, we have to access it through Drive C and then Drive E, which means first I have to go through all the files of Drive C and then through all the files of Drive E, and then we can finally access any file in Drive F.
Just Think of this situation, your life would have been pathetic.
Thanks to tree data structure.
This representation looks fine as we have access to all three other drivers from my computer, and this is where tree data structures come into play.
Binary Search Tree in Data Structure
In Linear Data Structures, such as Linked List, Searching takes O(n) time complexity. In Arrays inserting and deleting a data takes O(n) time complexity.
Although O(n) looks good but thinks of real-world examples where we deal with millions of records, here O(n) may not be sufficient for inserting, deleting, or searching data.
Here also trees play a vital role. Binary Search Tree is an application of Tree where insertion, deletion, and searching all takes O(log n) time complexity.
This is a Binary Search Tree, we will discuss it later but it is an application of Tree Data Structure.
There are millions of applications of Tree Data Structures in the real world. Let us now do some technical stuff.
Technical Definition of Tree
In a programming language, the tree is defined as a collection of nodes and edges. What is a node..?
Node is an entity which represents a tree, nodes are connected by edges and this overall combination forms a network which is known as a tree.
Types of Trees in Data Structure
Binary Tree in Data structure :
A tree where each node can have at most two children is called a binary tree. A binary tree can have at most (2^h – 1) numbers of nodes. The height of a tree is represented by ‘h’.
The height of a tree is the number of levels in a tree. In the given tree, ‘h’ is 3.
N-ary Tree: A tree where each node can have n children is called an N-ary tree.
Some Technical Terms
Root: Topmost Element of the tree is called the root of the tree.
Parent: The node which has a branch from it to any other node is called a parent node.
Child: The node which is a descendant of some node is called a child node.
Siblings: Nodes that belong to the same parent are siblings to each other.
Leaf Node: Nodes having no children is called a leaf node.
Internal Node: Nodes with at least one child are internal nodes.
Let us take an example,
In the above example,
(i) A is the root of the tree.
(ii) B is the parent of D and E.
(iii) C is a child of A.
(iv) B and C are siblings.
(v) D, E, G are leaf nodes.
(vi) A, B, C, and F are internal nodes.
As we have discussed earlier, the binary tree is a tree where each node can have at most 2 children. The two children are referred to as the left child and right child.
Now, you must be wondering how we can represent this tree data structure in our code..? Yes, this is an obvious question every beginner thinks of. There are two ways of representing a binary tree data structure. One is by using an array and the other is by using a doubly-linked list.
Representation of Binary Tree using an array
We will initially store the root in the 0th index. Since we know that a node in a binary tree can have at most two children. So we have to give two continuous slots for every root to store his left and right child.
So, we will store the left child of the root in ((2*i) + 1)th index and store the right child of the root in ((2*i) + 2)th index.
Let us consider an example,
Disadvantages of using Array Representation
- In array representation, we have to predefined the height of the tree so that maximum of (2^h-1) space can be allocated in the array for the binary tree representation. We have to fixed the size of the array initially which doesn’t allow us to grow our tree beyond.
- In array, memory wastage is a big issue. In the second example, we saw that the 4th and 6th index were unused. Just think of a large tree with millions of nodes, in that case, memory wastage will be a serious problem.
Representation of Binary Tree using Doubly Linked List
We are using a doubly-linked list because we require two pointers, one for the left child and another for the right.
struct Node *left;
struct Node *right;
Types of Binary Trees in Data Structure
Perfect Binary Tree:
It is a binary tree in which all levels are completely filled. It means every level must contain (2^l) nodes (level starting from 1).
A Perfect Binary Tree of height ‘h’ has 2h – 1 node.
Complete Binary Tree :
It is a binary tree in which all levels are completely filled except possibly the last level and keys at last level must have nodes as left as possible.
Every perfect Binary Tree is a complete tree but vice versa is not true.
That’s All Folks