Trees, Graphs:

1. What are Binary Trees? What are the advantages of Binary trees?

A Binary tree is a non-linear data structure in which each node has maximum of two child nodes.

2. What are the advantages of binary tree:

• Searching in a binary tree becomes faster

• Binary tree provides 6 traversals.

• Two of six traversals give sorted order of the elements

• Maximum and minimum elements can be directly picked up

• It is used for graph traversals and to convert an expression to postfix and prefix forms.

3. What are binary-tree traversals?

Binary tree provides six traversals, which include “in order”, “post order” and “pre order” traversals

4. What are Graphs? Explain types of graphs.

A graph is a collection of vertices or nodes, which are joined as pairs by lines or edges. Formally, a graph G = (V, E) is an ordered pair of finite sets of Vertices and Edges.

5. What are types of Graphs?

The types of graphs are listed below:

1. Directed Graph: A graph in which each edge is directed is called Directed graph.

2. Undirected graph: A graph in which each edge is undirected is called an undirected graph.

3. Connected graph: A graph G is connected if there is a path between every pair of vertices.

4. Sub graph: sub graph is a graph in which vertex and edge sets are subsets of those of G.

5. Complete Graph: A graph G is said to be complete if every vertex V is adjacent to every other vertex V in G. A complete graph with ‘n’ vertices has ‘n (n-1)/2’ edges.

6. Weighted graph: A graph ‘G’ is weighted, if each edge in G is assigned a nonnegative numerical value (cost or weight).

7. Connected directed graph or strongly connected graph: A directed graph G is said to be connected, or strongly connected, if for each pair of vertices (v1, v2) there is a path from v1 to v2 and v2 to v1.

6. What is a complete graph?

A graph G is said to be complete if every vertex V is adjacent to every other vertex V in G. A complete graph with ‘n’ vertices has ‘n (n-1)/2’ edges. For example. The following graph is an example for complete graph because it has 4 nodes and 6 ( ‘n (n-1)/2’ here, n=4 ) edges.

7. What are the applications of graphs?

• Analysis of electrical networks

• Study of molecular structure

• The representation of airlines routes

• Networks

• Topological sort

• Finding shortest paths

8. How do you represent a Graph?

A graph can be mainly represented in two ways.

1. Adjacency Matrix (this uses a double dimensional array)

2..Adjacency list (this uses linked lists

9. Explain Graph traversals. (OR) Explain Depth first and Breadth First Search methods.

There are mainly two methods for traversing in a graph, Depth first and Breadth first traversals.

1. Depth First Search (DFS): It uses a STACK to hold the nodes that are waiting to be processed. First we examine the starting node ‘A’. Then we examine each node along a path ‘P’, which begins at A. i.e. we process one of the neighbors of ‘A’ and continue along the path. After coming to the end of ‘P’, we back track on ‘P’ until we can continue along another path.

2. Breadth First Search (BFS): It uses QUEUE to hold nodes that are waiting to be processed. First we examine the starting node A. Then we examine all the neighbors of A. And, we continue with the other nodes in the same manner. No node is processed more the once.

10.Differentiate Graph and Tree.

Tree	Graph
A tree is a data structure in which each node is attached to one or more nodes as children	A graph is a collection of vertices or nodes, which are joined as pairs by lines or edges
This is a non linear data structure	This is a non linear data structure
All the trees can be graphs	All the graphs are not trees
It provides six different traversals	It provides two different traversals
It is undirected and connected	It can be directed or undirected; can be connected or not-connected
It cannot be cyclic	It can be cyclic or acyclic

11. What is a spanning tree?

A spanning tree is a subgraph of G (where G is undirected connected graph), is a tree, and contains all the vertices of G.

12. What is a minimum spanning tree?

A minimum spanning tree is a spanning tree, but has weights associated with the edges, and the total weight of the tree (the sum of the weights of its edges) is at a minimum.