Data Structures

Trees

• A Tree is a non linear data structure in which

items are arranged in a sequence.
• It is used to represent hierarchical relationship
existing among several data item

03:27:52 P 2
M
 Basic Terminology

03:27:52 P 3
M
03:27:52 P 4
M
03:27:52 P 5
M
03:27:52 P 6
M
03:27:52 P 7
M
03:27:52 P 8
M
03:27:52 P 9
M
03:27:52 P 10
M
 Representing Binary trees in Memory

• There are two ways representing binary trees in

memory:
1)Sequential Representation of binary trees
2)Linked Representation of Binary tree

03:27:52 P 11
M
 Binary Trees: Array representation
AIIT
Sequential Representation of binary Trees uses only a single linear array TREE together
with a pointer variable END as follows:
(a) The root R of T is stored in TREE[1].
(b) If a node occupies TREE[k], then its left child is stored in TREE[2 * K] and its right child is
stored in TREE[2*k+1]
(c) END contains the location of the last node of T.

03:27:53 P 12
M
 Linked Representation of Binary Tree AIIT

• The most popular way to present a binary tree

• Each element is represented by a node that has two link fields ( leftChild
and rightChild ) plus an Info field
• The space required by an n node binary tree is
n * sizeof(binaryTreeNode)

03:27:53 P 13
1 M
 Linked Representation of Binary trees
AIIT
1. INFO[K] contains the data at the node N
2. LEFT[K] contains the location of the left child of node N
3. RIGHT[K] contains the location of the right child of node N.

Fig : 7-6
03:27:53 P 14
M
 AIIT

03:27:53 P 15
M
 AIIT

03:27:53 P 16
M
 Arithmetic Expressions as trees(cont.) AIIT

Figure 11.5 Expression Trees

03:27:53 P 17
1 M
 Arithmetic Expressions as trees(cont.)
Example 7.2: Algebraic Expressions
Consider any algebraic expression E involving only binary operations,
such as
E = (a-b) / ((c * d) + e)
E can be represented by means of the binary tree T pictured in fig. 7.3.

- +

a e
b *

c d
Fig. 7.3: E = ( a – b ) / (( c * d ) + e )
03:27:53 P 18
M
03:27:53 P 19
M
03:27:53 P 20
M
 Application of Tree

1) Expression Tree: An application of tree is in compiler

and interpreter as well as in symbolic mathematics
programs. Here tree can be used to represent
arithmetic expressions.
2) Game tree: Another important application of tree is a
game tree. Here trees are used to represent all the
possible moves from a given board position and the
reason about what the best move is. An example of
game tree is tic tac toe game
3) Huffman Algorithm

03:27:53 P 21
M
 Binary Tree Traversal
• Many binary tree operations are done by performing a traversal of the binary tree AIIT
• In a traversal, each element of the binary tree is visited exactly once

03:27:53 P 22
2 M
 Algorithms

Algorithm Inorder(tree)
1. Traverse the left subtree, i.e., call Inorder(left-
>subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-
>subtree)

03:27:53 P 23
M
 Algorithm Preorder(tree)

1. Visit the root.

2. Traverse the left subtree, i.e., call Preorder(left-
>subtree)
3. Traverse the right subtree, i.e., call
Preorder(right->subtree)

03:27:53 P 24
M
 Algorithm Postorder(tree)

1. Traverse the left subtree, i.e., call Postorder(left-

>subtree)
2. Traverse the right subtree, i.e., call
Postorder(right->subtree)
3. Visit the root

03:27:53 P 25
M
03:27:53 P 26
M
03:27:53 P 27
M
03:27:53 P 28
M
03:27:53 P 29
M
03:27:53 P 30
M
 Conversion from Preorder and Inorder
traversal to construct a tree

03:27:53 P 31
M
03:27:53 P 32
M
 Conversion from post and pre order to
construct a tree

03:27:53 P 33
M
03:27:53 P 34
M
 Construct a tree from given inorder and
postorder

03:27:53 P 35
M
03:27:53 P 36
M
 Binary Search Tree (Con..) AIIT

A Binary Search Tree is a binary tree with the following Basic properties:

• All items in the left subtree are less than the root.
• All items in the right subtree are greater or equal to the root.
• Each subtree is itself a binary search tree.

37
Binary Search Trees AIIT

38
(Con..) AIIT
(Con..) AIIT
Prepared by, Jesmin Akhter, Lecturer, IIT,JU
Figure 1. Inserting a new node into a BST
A BST after nodes with values of 20, 50, 90, 150, 175, and 200 have been added
 Inserting a new key in a BST

How to insert a new key? Example:

The same procedure used for search 10

also applies: Determine the location
by searching. Search will fail. Insert 8
new key where the search failed. Insert 4?
3 9 4

2 5
 Building a BST

Build a BST from a sequence of nodes read one a time

Example: Inserting C A B L M (in this order!)

1) Insert C 2) Insert A
C
C
A
 Building a BST

3) Insert B C
5) Insert M
A
C
B
A L

4) Insert L C B M

A L

B
 Building a BST
Is there a unique BST for letters A B C L M ?
NO! Different input sequences result in different
trees

Inserting: A B C L M Inserting: C A B L M
A
C
B
C A L

L B M
M
 Sorting with a BST

Given a BST can you output its keys in sorted order?

Example:
Visit keys with Inorder:
- visit left
- print root C
- visit right

How can you find the minimum? A L

How can you find the maximum?
B M

Inorder visit prints:

A B C L M
 Inorder Traversal AIIT

12 18 20 23 35 44 52

Inorder traversal of a binary search tree produces a

sequenced list
49
 AIIT

03:27:54 P 50
M
 AIIT

03:27:54 P 51
M
 AIIT

03:27:54 P 52
M
 AIIT

03:27:54 P 53
M
 AIIT

03:27:54 P 54
M
 Program 24

• Write a Program to implement Binary Search

Tree
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#include<ctype.h>
typedef struct ntag
{
int item;
struct ntag *left, *right;
}node;

node* createnode(int x)
{
node *p;
p=(node*)malloc(sizeof(node));
if(p==NULL)
{
printf("\n Memory not Available");
exit(1);
}
p->item=x;
p->left=NULL;
p->right=NULL;
return p;
}
node* insert (node* root, node *n)
{
node *p;
if (root==NULL)
root=n;
else
{
p=root;
while (p!=NULL)
{
if(n->item < p->item)
{
if(p->left!=NULL)
p=p->left;
else
{
p->left=n;
break;
}
}
if (n->item > p->item)
{
if(p->right!=NULL)
p=p->right;
else
{
p->right=n;
break;
}
}
if (n-> item==p->item)
{
printf("\n Duplicate item");
exit(1);
}
}
}

return root;
void display (node *root)
{
node *p, *temp;
p=root;
if(p!=NULL)
{
printf("\n%d", p->item);
if(p->left !=NULL)
{
temp=p->left;
display(temp);
}
if(p->right !=NULL)
{
temp=p->right;
display(temp);
}
}
}
node* create_bst()
{
node* n= NULL;
node* root=NULL;
int x=0;
char choice;
do
{
printf("\n Enter item:");
scanf("%d", &x);
n=createnode(x);
if(n==NULL)
{
printf("\n Memory unavailable");
exit(1);
}
root=insert(root, n);
printf("\n Want to add more items (Y/N)");
fflush(stdin);
scanf("\n%c", &choice);
}while(toupper(choice)=='Y');
return root;
}
void main()
{
node* root;
root = create_bst();
display(root);
}
 Program 2

Write a program to traverse a BST

03:27:54 P 61
M
void preorder(node *root)
{
if (root!=NULL)
{
printf(“\n preorder %d”, root->item);
preorder(root->left);
preorder(root->right);
}
}
void postorder(node *root)
{
if (root!=NULL)
{
postorder(root->left);
postorder(root->right);
printf(“\n postorder %d”, root->item);
}
}
03:27:54 P 62
M
void inorder(node *root)
{
if (root!=NULL)
{

inorder(root->left);
printf(“\n inorder %d”, root->item);
inorder(root->right);
}
}

03:27:54 P 63
M
int main()
{
node *root;
root= create_BST();
preoder(root);
postorder(root);
inorder(root);
getch();
return 0;
}

03:27:54 P 64
M
 Formal Definition:
• A graph, G=(V, E), consists of two sets:
• a finite non empty set of vertices(V), and
• a finite set (E) of unordered pairs of distinct vertices called
edges.
• V(G) and E(G) represent the sets of vertices and edges of
G, respectively.
• Vertex: In graph theory, a vertex (plural vertices) or node or
points is the fundamental unit out of which graphs are
formed.
• Edge or Arcs or Links: Gives the relationship between the Two
vertices.

4/10/2017 6
5
 Examples for Graph

0 0 0

1 2 1 2
1
3
3 6
G 4 5
2
1 G2
G3
V(G1)={0,1,2,3} E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}
V(G2)={0,1,2,3,4,5,6} E(G2)={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)}
V(G3)={0,1,2} E(G3)={<0,1>,<1,0>,<1,2>}
4/10/2017 6
6
 Adjacent, neighbors
• Two vertices are adjacent and are neighbors if they are
the
endpoints of an edge
• Example:
• A and B are adjacent
• A and D are not adjacent

A B

C D
Graph Theory S Sameen Fatima 67
Degree

Degree: Number of edges incident on a node

A B C

D E F

The degree of B is 2.

Graph Theory S Sameen Fatima 68

 Degree (Directed Graphs)
• In degree: Number of edges entering a node
• Out degree: Number of edges leaving a node
• Degree = Indegree + Outdegree

1 2

4 5

The in degree of 2 is 2 and

the out degree of 2 is 3.

Graph Theory S Sameen Fatima 69

 Complete Graph
• A graph is said to be complete or
fully connected if there is a path
from every vertex to every other
vertex.

• A complete graph with n vertices will

have n(n-1)/2 edges.

• For eg:

• n=4
 Tree
• A graph is a tree, if it has following
two properties:
1)It is connected
2)There are no cycle in a graph
 Graph
Representation
• There are two standard ways of maintaining a
graph in a memory of a computer
1) Sequential Representation by means of
Adjacency Matrix
2) Linked Representation by means of linked list of
neighbours
SEQUENTIAL REPRESENTATION
OF GRAPHS
What is Sequential Representation of Graphs?

• In sequential representation, we use adjacency matrix

to store the mapping represented by vertices and
edges. In adjacency matrix, the rows and columns are
represented by the graph vertices. A graph having n
vertices, will have a dimension n x n.
• Graphs can be represented through matrix in system’s
memory. This is sequential in nature. This type of
representation is called Sequential Representation of
Graphs.
AIIT
 Adjacency Matrix Cont..

• The Adjacency matrix of the graph does not depend on the

ordering of the nodes of the graph
i.e, A different ordering of the nodes may result in a different
adjacency matrix. However the matrices resulting from different
ordering are related in that one can be obtained from other.
 Linked Representation of Graph
(Adjacency list Representation)
• The sequential representation of graph has many
drawbacks:
1) It may be difficult to insert and delete nodes in
graph. This is because the size of adjacency
matrix may need to be changed and the nodes
may need to be reordered. So, their may be many
many changes in the matrix
2) A lot of space is wasted as it is a sparse matrix
So, graph is usually represented in memory by
linked representation also known as Adjacency list
representation.
 Adjacency List Representation

• The linked representation will contain two list:

1) Node List: Each element in the list ‘node’ will correspond to a node in graph
and it will be record of the form:

Here NODE will be the name or key value of node

NEXT is a pointer to next node
ADJ is a pointer to the first element in the adjacency list of the node which is
maintained in the list EDGE
2) EDGE LIST: It is of the form:

DEST will point to the location in the list NODE of the destination node of the
EDGE
LINK will link together the edges with the same initial node.
Adjacency List Representation Cont…
03:27:54 P ----------------------------------------- 80
M
03:27:54 P 81
M
03:27:54 P 82
M
03:27:54 P 83
M
03:27:54 P 84
M
03:27:55 P --------------------------------------------------------------- 85
M
03:27:55 P 86
M
03:27:55 P 87
M
03:27:55 P --------------------------------------------------------------- 88
M
03:27:55 P 89
M
03:27:55 P --------------------------------------------------------------- 90
M
03:27:55 P --------------------------------------------------------------- 91
M
 Traversal of Graphs

• BFS (Breadth First Search)

• DFS (Depth First Search)

03:27:55 P 92
M
03:27:55 P --------------------------------------------------------------- 93
M
03:27:55 P --------------------------------------------------------------- 94
M
Thankyou .