DSA Oral QNA

Chapter 1: Tree

Q. What is tree?

Answer: A tree is a non-linear data structure where the data elements are stored in hierarchial form.

Q.Define: 

1. Binary Tree

Answer: A tree in which every node can have maximum two children is called as binary tree.

2. Skewed Binary Tree

Answer: A tree in which every node has either left subtree or only right subtree is called as skewed binary tree.

3. Strictly Binary Tree

Answer: It is a binary tree where all non-leaf nodes have two branches.

4. Full Binary Tree

Answer: It is a binary tree which has either two children or no child at all and all leaves are on same level.

5. Complete Binary Tree

Answer: It is  a binary tree where all of its levels except the last level have maximum number of possible nodes, and all nodes of the last level appear at far left.

6. Binary Search Tree

Answer: It is a binary tree where nodes are arranged according to its values. Nodes with values less than the root are in the left subtree and greater than root are in the right subtree.

7.Heap

Answer: It is a tree based data structure where the tree is a complete binary tree. It can be max heap (root is greatest element) or min heap (root is smallest element).

Q. What are tree traversals?

Answer: It is the process of visiting each and every node of tree exactly once. It can be preorder(Data->left->right) , Inorder (left->data->right) or postorder (left->right->data.).

Chapter 3: Graph

Q. Define.

1. Graph

Answer: A graph is a pair of sets (V,E), where V is a set of vertices and E is a set of edges, connecting the pair of vertices.

2. Directed Graph

Answer: Here each edge is represented by a directed pair (v1,v2) , v1 is the tail and v2 is the head of the edge. i.e. (v1,v2) and (v2,v1) are different edges.

3. Undirected Graph

Answer: Here the pair of vertices representing any edge is unordered , ie.e. (v1,v2) and (v2,v1) represent same edge.

4. What is adjacent vertex?

Answer: When there is an edge from one vertex to another then these vertices are called adjacent vertices. 

5. What are ways of representation of a graph?

Answer: Graphs can be represented as following:

1. Sequential representation (using Adjacency Matrix)

2. Linked representation (using Adjacency List)

3. Inverse Adjacency list

4. Adjacency multilist 

6. What are graph Traversals?

Answer: Graph traversal means visitng every vertex and edge exavtly once in an order. It can be done using :

Depth First Search (DFS) : All the vertics are stored in a stack and each vertex of the graph is visited and explored once. The newest vertex (added last) in stack is visited first.

Breadth First Search (BFS): Here all the vertices are stored in a queue and each vertex of the graph is visited and explored one. The oldest vertex (added first) in queue is explored first.