Tree : Data Structure

• The data in a tree are not stored in a sequential manner i.e., they are not stored linearly.
Instead, they are arranged on multiple levels or we can say it is a hierarchical structure. For
this reason, the tree is considered to be a non-linear data structure.

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

• The topmost node of the tree is called the root, and the nodes below it are called the child
nodes. Each node can have multiple child nodes, and these child nodes can also have their
 Basic Terminologies In Tree Data Structure:
• Parent Node: The node which is a predecessor of a node is called the parent node of that node. {B} is the parent node
of {D, E}.
• Child Node: The node which is the immediate successor of a node is called the child node of that node. Examples: {D,
E} are the child nodes of {B}.
• Root Node: The topmost node of a tree or the node which does not have any parent node is called the root node. {A} is
the root node of the tree. A non-empty tree must contain exactly one root node and exactly one path from the root to
all other nodes of the tree.
• Leaf Node or External Node: The nodes which do not have any child nodes are called leaf nodes. {K, L, M, N, O, P, G}
are the leaf nodes of the tree.
• Ancestor of a Node: Any predecessor nodes on the path of the root to that node are called Ancestors of that node.
{A,B} are the ancestor nodes of the node {E}
• Descendant: A node x is a descendant of another node y if and only if y is an ancestor of y.
• Sibling: Children of the same parent node are called siblings. {D,E} are called siblings.
• Level of a node: The count of edges on the path from the root node to that node. The root node has level 0.
• Internal node: A node with at least one child is called Internal Node.
• Neighbour of a Node: Parent or child nodes of that node are called neighbors of that node.
• Subtree: Any node of the tree along with its descendant.
Properties of Tree Data Structure:

• Number of edges: An edge can be defined as the connection between two nodes. If a tree has N nodes
then it will have (N-1) edges. There is only one path from each node to any other node of the tree.
• Depth of a node: The depth of a node is defined as the length of the path from the root to that node.
Each edge adds 1 unit of length to the path. So, it can also be defined as the number of edges in the path
from the root of the tree to the node.
• Height of a node: The height of a node can be defined as the length of the longest path from the node to
a leaf node of the tree.
• Height of the Tree: The height of a tree is the length of the longest path from the root of the tree to a
leaf node of the tree.
• Degree of a Node: The total count of subtrees attached to that node is called the degree of the node. The
degree of a leaf node must be 0. The degree of a tree is the maximum degree of a node among all the nodes
in the tree.
 Representation of Tree Data Structure:
Representation of a Node

struct Node
{
int data;
struct Node *first_child;
struct Node *second_child;
struct Node *third_child;
.
.
.
struct Node *nth_child;
};
Types of Tree
data structures:

❑ According to
Number of
Children

On the basis of number of children

Ternary Search Tree(TST)
• Full Binary Tree (Generic Tree)
• Degenerate Binary Tree
On the basis of completion levels
• Perfect Binary Tree
• Complete Binary Tree
• Balanced Binary Tree
❑ According to the Nodes Values
1. Binary Search Tree

2. AVL Tree

3. B-Tree

4. B+ Tree
• Binary Tree: A binary tree is a type of general tree, except,
with a constraint - a node can have at most two child nodes.
The children nodes are known as the left child node and right
child node.

struct node {
int data;
struct node* left;
struct node* right;
};

On the basis of number of children binary tree has two types:

• Full Binary Tree: All the internal nodes of a full binary tree
have two or no child nodes.

• Degenerate Binary Tree: Every internal node of the

degenerate binary has just one child.
The binary tree can be divided into three
types on the basis of completion levels:

• Perfect Binary Tree: All the leaf nodes

of this tree are at the same level. Every
internal node of a perfect binary tree
has 2 child nodes.

• Complete Binary Tree: Every level

except the last one are full of nodes

• Balanced Binary Tree: The difference in

height between the left and right
subtrees of any node is either 0 or 1.
• Ternary Tree
Each node can have a maximum of three child nodes.,
commonly referred to as "left", "mid", and "right".

• N-ary Tree (Generic Tree)

Each node holds data records and references to its children. It
prohibits duplicate references among its children.

Key features of an N-ary tree:

• Each node can have multiple children.
• The exact number of children for each node is not
predetermined and may vary.
Binary Search Tree

A binary search tree shares similarities with a binary tree but has specific limitations. The value of the
left child in a binary search tree is always smaller than that of the parent node, and the value of the
right child is larger than that of the parent node in the binary search tree. This property makes the
binary search tree optimal for search operations.
AVL Tree
• A self-balancing binary search tree is called an
AVL tree.
• A Binary Search Tree is in balance when the
difference in height between left and right
subtrees is less than 2.
• In an AVL tree, a balancing factor is given to every
node in the tree
• balancing factor values vary between -1, 0, and 1.

BF(X)=
height(rightSubtree(X))−height(leftSubtree(X))
Binary Tree

A binary tree can be represented using

• array representation
• Linked List Representation

Binary Tree Operations:

• Inserting an element.
• Removing an element.
• Searching for an element.
• Deletion for an element.
• Traversing an element.
 • Create a New Node struct node* create(value)
of the Binary Tree {
struct node* newNode = malloc(sizeof(struct node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode; }

// Insert on the left of the node // Insert on the right of the node
struct node* insertLeft (struct node* root, int value) struct node* insertRight (struct node* root, int value)
{ {
root->left = create(value); root->right = create(value);
return root->left; return root->right;
} }
Tree traversal :
-used to traverse or visit the nodes of a tree.
-Using the root node, we can access every node of the tree if the tree is
connected, but we cannot randomly select a node.
Binary Tree Traversals:
1. Depth-First Search (DFS) Algorithms
i. Preorder Traversal
ii. Inorder Traversal
iii. Postorder Traversal
2. Breadth-First Search (BFS) Algorithms
1. Depth First Search (DFS) Algorithm

Depth-First Search is an important algorithm for traversal of binary tree. It starts with the
root node and first visits all nodes of one branch as deep as possible of the chosen node and
before backtracking, it visits all other branches in a similar fashion.
To traverse binary trees with depth-first search, the following operations are performed at
each node:
Algorithm:
2. If the current node is empty, then simply return.
3. Execute the following three operations in a particular order:
• N: Visit the current node.
• L: Recursively traverse the current node's left subtree.
• R: Recursively traverse the current node's right subtree.
i) Inorder Tree Traversal

• The inorder tree traversal of binary tree is also known as the LNR traversal, because in
this traversal, we first visit the left node (abbreviation L), followed by the root
node(abbreviation N), and finally the right node (abbreviation R) of the tree.

• The algorithm for the inorder traversal can be stated as:

1. Recursively traverse the current node's left subtree.

i.e., call Inorder(left->subtree)

2. Visit the current node.

3. Recursively traverse the current node's right subtree.

i.e., call Inorder(right->subtree)

ii) Preorder Tree Traversal

• In the case of the preorder traversal of binary tree, we visit the current node first. After that,
we visit the leftmost subtree. Once we reach the leaf node(or have covered all the nodes of
the left subtree), we move towards the right sub-tree. In the right subtree, we recursively call
our function to do the traversal in a similar manner.

• The algorithm for the preorder traversal of binary tree can be stated as:

1. Visit the current node

2. Recursively traverse the current node's left subtree.

i.e., call Preorder(left->subtree)

3. Recursively traverse the current node's right subtree.

i.e., call Preorder(right->subtree)

iii) Postorder Traversal

- we basically visit the left subtree and the right subtree before visiting the current node
in recursion.

- Postorder follows the L->R->N order of traversing the binary tree.

Algorithm

1. Recursively traverse the current node's left subtree.

i.e., call Postorder(left->subtree)

2. Recursively traverse the current node's right subtree.

i.e., call Postorder(right->subtree)

3. Visit the current node

Breadth First Search (BFS) / Level order:
• It starts from the root node and visits all nodes of the current depth before moving to the next
depth in the tree.
Algorithm:
1. Start at the root node and add it to a queue.
2. While the queue is not empty, dequeue a node
and visit it.
3. Enqueue all of its children (if any) into the queue.
4. Repeat steps 2 and 3 until the queue is empty

This approach ensures that nodes are visited level by level, moving horizontally across the tree
before moving to the next level. This way, BFS explores the nodes in a breadth-first manner,
making it useful for tasks like finding the shortest path in unweighted graphs or trees.
 Difference Between BFS and DFS

Parameters BFS DFS

Stands for BFS stands for Breadth First Search. DFS stands for Depth First Search.
Data BFS(Breadth First Search) uses Queue DFS(Depth First Search) uses Stack data
Structure data structure for finding the shortest path. structure.
DFS is also a traversal approach in which
BFS is a traversal approach in which we the traverse begins at the root node and
Definition first walk through all nodes on the same proceeds through the nodes as far as
level before moving on to the next level. possible until we reach the node with no
unvisited nearby nodes.
Conceptual
BFS builds the tree level by level. DFS builds the tree sub-tree by sub-tree.
Difference
Approach It works on the concept of FIFO (First In It works on the concept of LIFO (Last In
used First Out). First Out).
BFS is more suitable for searching vertices DFS is more suitable when there are
Suitable for
closer to the given source. solutions away from source.
DFS is used in various applications such
BFS is used in various applications such
Applications as acyclic graphs and finding strongly
as shortest paths
connected components etc.
 Binary Search Tree
• A binary Search Tree is a binary tree where the value of any node is greater than the left
subtree and less than the right subtree.
Properties
• All nodes of the left subtree are less than the root node and nodes of the right subtree
are greater than the root node.
• The In-order traversal of binary search trees gives the values in ascending order.
• All the subtrees of BST hold the same properties. struct Node {
int key;
struct Node *left, *right;
};

key: It will be the data stored.

left: Pointer to the left child.
right: Pointer to the right child
1. Search Operation on BST
struct Node* searchNode(struct Node* root, int target)
{
if (root == NULL || root->key == target)
{
return root;
}
if (root->key < target)
{
return searchNode(root->right, target);
}
return searchNode(root->left, target);
}
 2. Insertion in BST
• The insertNode function inserts a new node with a specific value into a Binary Search
Tree while maintaining the binary search tree property.
// Function to insert a node with a specific value in the tree
// Function to create a new node with a given struct Node* insertNode (struct Node* node, int value)
value {
struct Node* Create(int value) if (node == NULL)
{ {
struct Node* temp return Create(value);
= (struct Node*) }
malloc (sizeof(struct Node)); if (value < node->key) {
node->left = insertNode(node->left, value);
temp->key = value; }
temp->left = NULL; else if (value > node->key) {
temp->right=NULL; node->right = insertNode(node->right, value);
}
return temp; return node;
Delete a Node – delete() Method
There are three cases to delete the node from the tree.
• case 1: Deleting the leaf node
To delete the leaf node we need to traverse to the required leaf node then delete
that node and update its parent.
Example: Deleting a leaf node 65.
• case 2: Delete a node with one child
Remove that given node and replace it with its children.
Example: Deleting node 25, to delete node 25, we have to update it with its
children node 65.
• case 3: Deleting a node with two children
In this case, find the inorder successor of the node to which it is deleting.

Copy the content of the inorder successor node to the node.

Delete the inorder successor.

For this case, we can also use the inorder predecessor.

Example: Deleting node 8 from the given tree.

Application of Tree Data Structure:
• File System: This allows for efficient navigation and organization of files.

• Data Compression: Huffman coding is a popular technique for data compression that involves
constructing a binary tree where the leaves represent characters and their frequency of occurrence.
The resulting tree is used to encode the data in a way that minimizes the amount of storage required.

• Compiler Design: In compiler design, a syntax tree is used to represent the structure of a program.

• Database Indexing: B-trees and other tree structures are used in database indexing to efficiently
search for and retrieve data.
Advantages of Tree Data Structure:
• Tree offer Efficient Searching Depending on the type of tree, with average search times of O(log n) for
balanced trees like AVL.

• Trees provide a hierarchical representation of data, making it easy to organize and navigate large amounts
of information.

• The recursive nature of trees makes them easy to traverse and manipulate using recursive algorithms.

Disadvantages of Tree Data Structure:

• Unbalanced Trees, meaning that the height of the tree is skewed towards one side, which can lead to
inefficient search times.

• Trees demand more memory space requirements than some other data structures like arrays and linked
lists, especially if the tree is very large.

• The implementation and manipulation of trees can be complex and require a good understanding of the