VIDHYA SAGAR WOMENS COLLEGE, CHENGALPATTU
DEPT OF COMPUTER SCIENCE
ONLINE CLASS
DATA
STRUCTURE
Staff Incharge: D.Preethi M.Sc.,M.Phil.,NET
Asst.Professor
Dept of Computer Science
UNIT-4
Objectives
To Understand the concept of
Trees:
Binary Trees
Definitions
Binary Search Tree
Conversion of Forest to Binary
Tree operations
Tree Traversals
TREES IN DATA STRUCTURES
A tree is a nonlinear hierarchical data
structure that consists of nodes connected by
edges.
A node is a structure which may contain a
value, a condition, or represent a separate
data structure
Edge is nothing but connection between
node.
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 increase in the data size. But, it is
not acceptable in today's computational
world.
Different tree data structures allow quicker
and easier access to the data as it is a non-
linear data structure.
ADVANTAGES OF TREES
Trees are so useful and frequently used,
because they have some very serious
advantages:
Trees reflect structural relationships in the
data
Trees are used to represent hierarchies
Trees provide an efficient insertion and
searching
Trees are very flexible data, allowing to move
subtrees around with minumum effort
APPLICATIONS OF TREE
Trees are used to store simple as well as
complex data. Here simple means an integer
value, character value and complex data
means a structure or a record.
Trees are often used for implementing other
types of data structures like hash tables, sets,
and maps.
Trees are an important data structure used for
compiler construction.
Trees are also used in database design.
Trees are used in file system directories.
Trees are also widely used for information
storage and retrieval in symbol tables.
TREE TERMINOLOGIES
Node : Each data item in a tree is called a
node.
Edge: It is the link between any two
nodes.That is, the line drawn from one node
to another node is called an edge.
Root : It is the first in the hierarchical
arrangement of data items.
The root node is the topmost node in the tree.
Root
Parent − Any node except the root node has
one edge upward to a node called parent.
Child − The node below a given node
connected by its edge downward is called its
child node.
Leaf − The node which does not have any
child node is called the leaf node.
Subtree − Subtree represents the
descendants of a node.
Degree of a Node:The degree of a node is
the total number of branches of that node.
Degree of a Tree : The degree of a tree is
defined as the maximum of degree of the
nodes of the tree, that is, degree of tree =
max (degree(node i) for I = 1 to n)
Terminal node : A node with degree zero is
call a terminal node or a leaf.
Non-terminal node : Any node (except the
root node) whose degree is not zero is called
non-terminal node.
Siblings : The children nodes of a given
parent node are called siblings.
Levels − Level of a node represents the
generation of a node. If the root node is at
level 0, then its next child node is at level 1,
its grandchild is at level 2, and so on.
Path : It is a sequence of consecutive edges
from the source node to the destination
node.
Depth of node:The depth of a node is the
number of edges from the root to the node.
Height of a Node
The height of a node is the number of edges
from the node to the deepest leaf
Height of a Tree:The height of a Tree is the
height of the root node or the depth of the
deepest node.
Forest : It is a set of disjoint tree. In a given
tree, if you remove its root node then it
becomes a forest.
TYPES OF TREES
Binary Tree
Binary search trees
AVL tree or height balanced binary tree.
B-Tree
Expression trees
Tournament trees
BINARY TREE
A binary tree is a tree data structure in which each
parent node can have at most two children.
It is the leaf on the left which has a lesser key value,
and it is the leaf on the right which has an equal or
greater key value
for example: In the image below, each element has at most
two children.
Binary Tree
A tree is said to be binary tree when,
1. A binary tree has a root node. It may not
have any child nodes(0 child nodes, NULL
tree).
2. A root node may have one or two child
nodes. Each node forms a binary tree itself.
3. The number of child nodes cannot be more
than two.
4. It has a unique path from the root to every
other node.
TYPES OF BINARY TREE
Full Binary Tree
Perfect Binary Tree
Complete Binary Tree
Degenerate or Pathological Tree
Skewed Binary Tree
Balanced Binary Tree
Extended Binary Tree
FULL BINARY TREE
A full Binary tree is a special type of binary
tree in which every parent node/internal
node has either two or no children
Full binary tree is also called as Strictly
Binary Tree.
It is also known as a proper binary tree.
Full Binary Tree
PERFECT BINARY TREE
A perfect binary tree is a type of binary tree
in which every internal node has exactly two
child nodes and all the leaf nodes are at the
same level.
Perfect Binary Tree
COMPLETE BINARY TREE
A complete binary tree is just like a full binary
tree, but with somemajor differences
Every level must be completely filled
All the leaf elements must lean towards the
left.
The last leaf element might not have a right
sibling i.e. a complete binary tree doesn't
have to be a full binary tree.
Complete Binary Tree
DEGENERATE OR PATHOLOGICAL
TREE
A degenerate or pathological tree is the tree
having a single child either left or right.
Degenerate Binary Tree
SKEWED BINARY TREE
A skewed binary tree is a
pathological/degenerate tree in which the
tree is either dominated by the left nodes or
the right nodes.
Thus, there are two types of skewed binary
tree: left-skewed binary tree and right-
skewed binary tree.
Skewed Binary Tree
BALANCED BINARY TREE
It is a type of binary tree in which the
difference between the left and the right
subtree for each node is either 0 or 1.
Balanced Binary Tree
EXTENDED BINARY TREE
Extended binary tree consists of replacing
every null subtree of the original tree with
special nodes.
Empty circle represents internal node and
filled circle represents external node.
In an extended binary tree, nodes having two
children are called internal nodes and nodes
having no children are called external nodes.
BINARY TREE REPRESENTATION
A node of a binary tree is represented by a
structure containing a data part and two
pointers to other structures of the same type.
struct node {
int data;
struct node *left;
struct node *right;
};
BINARY TREE APPLICATIONS
For easy and quick access to data
In router algorithms
To implement heap data structure
Syntax tree
BINARY SEARCH TREES
A binary search tree is also a kind of binary
tree in which the nodes are arranged in an
order.
A BST is a binary tree where nodes are
ordered in the following way:
Each node contains one data
The data in the left subtree are less than the
data in its parent node
The data in the right subtree are greater the data
in its parent node
Binary search tree is a data structure that
quickly allows us to maintain a sorted list of
numbers.
A BINARY SEARCH TREE HAS THE FOLLOWING 2
CHARACTERISTICS FOR EVERY NODE N IN THE TREE:
•Every element in n's left subtree is less or equal to the
element in node n.
•Every element in n's right subtree is greater than the
element in node n.
OPERATIONS ON BST
Search
Insertion
Deletion
SEARCH OPERATION
The algorithm depends on the property of
BST that if each left subtree has values below
root and each right subtree has values above
the root.
If the value is below the root, we can say for
sure that the value is not in the right subtree;
we need to only search in the left subtree
if the value is above the root, we can say for
sure that the value is not in the left subtree;
we need to only search in the right subtree.
ALGORITHM:
If root == NULL
return NULL;
If number == root->data
return root->data;
If number < root->data
return search(root->left)
If number > root->data
return search(root->right)
INSERT OPERATION
Inserting a value in the correct position is
similar to searching because we try to
maintain the rule that the left subtree is
lesser than root and the right subtree is
larger than root.
We keep going to either right subtree or left
subtree depending on the value and when we
reach a point left or right subtree is null, we
put the new node there.
ALGORITHM:
If node == NULL
return createNode(data)
if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
return node;
DELETION OPERATION
There are three cases for deleting a node
from a binary search tree.
Case I
In the first case, the node to be deleted is the
leaf node. In such a case, simply delete the
node from the tree.
4 to be deleted
CASE II
In the second case, the node to be deleted
lies has a single child node. In such a case
follow the steps below:
Replace that node with its child node.
Remove the child node from its original
position.
6 to be deleted
Copy the value of child
Final tree
CASE III
In the third case, the node to be deleted has
two children. In such a case follow the steps
below:
Get the inorder successor of that node.
Replace the node with the inorder successor.
Remove the inorder successor from its
original position.
3 to be deleted
Copy the value of the inorder successor (4) to
the node
Delete the inorder successor
TREE TRAVERSAL
Traversing a tree means visiting every node
in the tree.
inorder, preorder and postorder
Preorder Traversal − Traverses a tree in a
pre-order manner.
Inorder Traversal − Traverses a tree in an
in-order manner.
Postorder Traversal − Traverses a tree in a
post-order manner.
Every tree is a combination of
A node carrying data
Two subtrees
INORDER TRAVERSAL
First, visit all the nodes in the left subtree
Then the root node
Visit all the nodes in the right subtree
Algorithm:
inorder(root->left)
display(root->data)
inorder(root->right)
INORDER:5 -> 12 -> 6 -> 1 -> 9
PREORDER TRAVERSAL
Visit root node
Visit all the nodes in the left subtree
Visit all the nodes in the right subtree
Algorithm:
display(root->data)
preorder(root->left)
preorder(root->right)
PREORDER:1->12->5->6->9
POSTORDER TRAVERSAL
Visit all the nodes in the left subtree
Visit all the nodes in the right subtree
Visit the root node
Algorithm:
postorder(root->left)
postorder(root->right)
display(root->data)
POSTORDER:5->6->12->9->1
TREE TRAVERSAL USING C++
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
Node(int data) {
this->data = data;
left = right = NULL;
}
};
// PREORDER TRAVERSAL
void preorderTraversal(struct Node* node) {
if (node == NULL)
return;
cout << node->data << "->";
preorderTraversal(node->left);
preorderTraversal(node->right);
}
// POSTORDER TRAVERSAL
void postorderTraversal(struct Node* node) {
if (node == NULL)
return;
postorderTraversal(node->left);
postorderTraversal(node->right);
cout << node->data << "->";
}
// INORDER TRAVERSAL
void inorderTraversal(struct Node* node) {
if (node == NULL)
return;
inorderTraversal(node->left);
cout << node->data << "->";
inorderTraversal(node->right);
}
int main() {
struct Node* root = new Node(1);
root->left = new Node(12);
root->right = new Node(9);
root->left->left = new Node(5);
root->left->right = new Node(6);
cout << "Inorder traversal ";
inorderTraversal(root);
cout << "\nPreorder traversal ";
preorderTraversal(root);
cout << "\nPostorder traversal ";
postorderTraversal(root);
return 0;
}
Conversion of Forest to Binary
Forest : It is a set of disjoint tree
Binary tree is a tree data structure in which
each parent node can have at most two
children
A
B C D
G
E
H I
F
forest tree
ALGORITHM
1.Convert each tree to a binary tree
2.The first binary tree doesn’t move
Starting from the second binary tree, the root node
of the later binary tree is used as the right child of
the root node of the previous binary tree, and
connected by lines
B E
C F G
H
D
I
Binary Tree
