Tree -A tree is a finite set of nodes with one specially designated node called the root and the

remaining
nodes are partitioned into n >= 0 disjoint sets T, and T, which are called the sub trees of the [Link]
Tree -A tree with no nodes is a Null Tree. It is also called an empty [Link] -A node of a tree is an item
of information along with the branches to other [Link] node -A parent node is a node having
other nodes connected to it. These nodes are called the children of that node. The root is the parent of
all its [Link] node -A leaf node is a terminal node of a tree. It does not have any children i.e. no
nodes connected to [Link] -Children of the same parent are called [Link] of a node -The
number of subtrees of a node is called its degree. The degree of leaf nodes is [Link] of the tree -
The degree of a tree Is the maximum degree of the nodes in the [Link] -The descendents of
a node are all those nodes which are reachable from that [Link] -The ancestors of a node are
all the nodes along the path from the root to that [Link] of a node -This indicates the position of a
node in the hierarchy. The level of any node = level of its parent +1. The root is considered to be at level
[Link] or Depth of a Tree -The total number of levels In the tree is the height or depth of the
[Link] -A forest Is a set of n >= 0 disjoint trees ie. If we remove the root, we get a forest of trees.

Static representation -Uses [Link] memory is not required to store links to [Link]
[Link] only if the tree is perfect or [Link] node can be directly accessed by calculating the
[Link] [Link] representation -Uses linked [Link] memory is required to
store links to [Link] [Link] for any type of tree.A node cannot be accessed directly. To
reach A node, we have to start from the root and use The links to that [Link] representation.

Preorder Traversal -void preorder (NODE *root){ NODE *temp =root; if (temp!= NULL){ Printf(“\d\t”,
temp->info); preorder (temp->left);Preorder (temp->right); }}

Inorder Traversal -void inorder (NODE * root){ NODE *temp = root; if (temp != NULL){ Inorder (temp-
>left);print(“%d\t”, temp->info); Inorder (temp->right); }}

Postorder Traversal -Void postorder (NODE root){ NODE temp root;if (temp != NULL){ postorder (temp-
>left);postorder (temp->right);printf("\t", temp->info); }}

Mirror -Void mirror (NODE root){ NODE* temp= root, *temp1; if(temp!=NULL) { If (temp->left!-NULL)
mirror (temp->left); If (temp->right!-NULL) mirror (temp->right);Temp1=temp->left; Temp->left =temp-
>right; temp->right=temp1;

Heap Sort -Heapsort is one application of binary tree. This sorting method uses a special type of binary
tree called “Heap”. A max-heap is a full or complete binary tree such that each parent has a value
greater than its children. This implies that the largest elem is in the root node.

Greedy Strategy - The Greedy strategy is an important algorithm design strategy that is used in problem
solving. It Is used to solve optimization problems where the goal is to maximize (or minimize) an
objective.

Hoffman Encoding -Encoding is the process of assigning a binary value to a symbol so that it can be
stored and transmitted on a computer [Link] concept of variable-length encoding is to encode
each character according to its frequency of [Link] coding is a lossless data compression
algorithm which is based on the Greedy strategy.
Graph -A graph, G, is a collection of two sets V and E. V is a finite non-empty set of vertices (or nodes)
and E is a finite non-empty set of edges (or arcs) connecting a pair of vertices. An edge is represented by
two adjacent vertices. G is represented as G = (V,E).

Degree of Vertex -The degree of a vertex in an undirected graph is the total number of edges that vertex
is connected [Link] of a Vertex -If G is a directed graph, the indegree of a vertex is the number of
edges for which it is head, i.e. The number of incoming edges to the vertex. A node whose indegree is 0,
is called a source [Link] of a Vertex -If G is a directed graph, the outdegree of a vertex is the
number of edges for which it Is the tail.i.e., the number of edges going out of it. A node whose
outdegree is 0, is called a sink [Link] -A path from vertex V, to V, exists if there exist vertices Va. VaV
such that there exist edges (V, Va). (Vu. Va…(VV).Length of a Path -The length of a path Is the number of
edges on [Link] Path- A linear path is a path whose first and last vertices are [Link]- A cycle in
a path whose first and last vertices are identical. A graph with no cycles is called an Cydic
[Link] Graph -Two vertices, V, and V, are said to be connected if there is a path in G from V,
to [Link]- A subgraph of G is a graph G, such that V(G) V(G) and E(G) E(G).Weighted Graph or
Network -A number (weight) may be associated with each edge of a graph. Such a graph is called a
which it is the weighted graph or a network. The number may represent the distance, cost, [Link]
Tree -A spanning tree is a subset of a graph with all vertices and n-1 edges such that they connect all The
vertices. This subset forms a tree.

Depth First Search -Traverses a graph [Link] a stack for [Link] of a node is
suspended another unexplored is [Link] is faster and requires lesser memory. The DFS traversal tree
is narrow and [Link] First Search -Traverses a graph [Link] a queue for traversal.A node
is fully explored before any other can [Link] is slower and requires more [Link] BFS traversal
tree is wide and short.

Program: DFS of Graph - #include<stdio.h> vold recdfs(int m[10] [10], int n, int v) { int w; Static int
visited[201=(0);Visited[v]=1;Printf(“v%d “, v+1); for (w=0;w<n; w++) { If((m[v] [w]==1) && (visited
[w]==0)) recdfs (m, n, w); }} Void main() { Int m[5][5]= ((0,0,1,1,0), (0,0,1,0,1), (0,1,0,0,0), (0,0,0,0,1),
(0,0,0,0,0));Printf(“\nThe Depth First Search traversal is :”); Recdfs (m, 5, 0); }

Program: BFS of Graph -#include<stdio.h> void bfs( int m[10] [10], int n) { Int I, j,v,w int visited[20] = (0);
QUEUE q; initq(&q); Printf(“\nThe Breadth first traversal is :\n”); V=0; Visited[v]-1; addq (&q, v); While
(!isempty (&q)) { v=removeq (&q); printf(“ vid,v+1); for (w-0;w<n; w++) if((m[v] [w]=-1) && (visited [w]—
0)) { addq(&q, w); visited[w]=1; }}} void main() { int m[5][5]=((0,0,1,1,0), (0,0,1,0,1), (0,1,0,0,0),
(0,0,0,0,1),(0,0,0,0,0));Bfs (m, 5); }

AOV Network Topological Sort - A directed graph in which the vertices represent activities or tasks and
the edges represent the precedence is called an AOV [Link] Sort Definition: The process
of converting a set of precedences represented by an AOV network into a linear list in which no later
activity precedes an earlier one is called Topological Sorting.

Dijkstra's Shortest Path Algorithm -void dijkstra int v, int n) { Int I, j,u,w, count, min; Int dist (10),
visited[10]=(0); visited[v]=1; For (i=0;i<n;i++) dist [i]-cost (v) [i]; Count=2; while (count <n) { Min-999;
For (i=0;i<n;i++) if (visited[i]==0 && dist[i] <min) { min=dist [1]; u=i; } Visited[u]=1; for (w=0; w<n;
w++) If (dist [u] +cost [u] [w]<dist[w]) dist (w)-dist [u] +cost [u] [w]; Count++; } Printf(“\nShortest
distances from vertex d are: \n”,v);for (i=0; i<n; i++) printf("\t", dist[i]); } void main( { dijkstra (4,8); }