-------------TREES-----------------
1. What is Binary Tree?
->A binary tree is a 2-ary tree in which each node(N) has atmost 2 children (either 0 or 1). The node with 2 children are called internal nodes, and the nodes with 0 children are called external nodes or leaf nodes.
2. What is Complete Binary Tree?
->A Binary tree is complete binary tree if all levels are completely filled except possibly the last/lowest level are full and in the last/lowest level all the items are on the left.
3. What is Perfect Balanced Binary Tree?
->A perfect balanced binary tree is a binary tree where each node has same number of nodes in both subtrees.
13. Define Height in a tree?
-> Height is a general measured as number of edges from the root to deepest node in the tree.
14. What is tree traversal?
->Traversal is used to visit each node in the tree exactly once. A full traversal of a binary tree gives a linear ordering of the data in the tree. There are 3 different type of tree traversal: 1. Inorder Traversal
2. Preorder Traversal
3. Postorder Traversal
15. How does Inorder Traversal work?
->1. Traverse the left sub tree of the root node R in inorder.
2. Visit the root node R.
3. Traverse the right sub tree of the root node R in inorder.
16. How does Preorder Traversal work?
->1. Traverse the left sub tree of the root node R in preorder.
2. Traverse the right sub tree of the root node R in preorder.
3. Visit the root node R.
17. How does Postorder Traversal work?
->1. Visit the root node R.
2. Traverse the left sub tree of the root node R in postorder.
3. Traverse the right sub tree of the root node R in postorder.
18. What is a Binary Search Tree?
->A BST(Binary Search Tree) is a binary tree in which each node satisfies search property. Each node's key value must be greater than all values in its left subtree and must be less than all values in its right subtree.
19. What is a AVL Tree?
-> AVL tree is a self-balancing binary search tree with height-balanced condition. For every node the height of left subtree and right subtree can be differ by at most 1.
20. What is a B-tree?
->A B-Tree is a tree data structure that keeps data sorted and allows searches, insertions, deletions, and sequential access in logarithmic amount of time. In B-Tree, internal nodes can have a variable number of child nodes within some pre-defined range. A B-tree is kept balanced by requiring that all leaf nodes are at the same depth. A B-tree of order m is a tree which satisfies the following properties:
1. Every node has atmost 2m children.
2. Every node (except root and leaves) has atleast m children.
3. The root has atleast two children if it is not a leaf node.
4. All leaves appear in the same level, and carry information.
5. A non-leaf node with k children contain k-1 keys.
6. Leaf nodes contain atleast m-1 children and atmost 2m-1 keys.
21. What is a B+ Tree?
->A B+ Tree is a tree data structure which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic multilevel index, with maximum and minimum bounds on the number of keys in each segment (usually called a 'block' or 'node')
22. What is a Binary Heap Tree?
->A Binary Heap tree is a balanced binary tree where root node are compared with its children and placed accordingly. Heap have two properties namely, structure and order property.
36. Explain algorithm for finding Minimum Spanning Tree?
-> There are 2 widely used algorithm for finding minimum spanning tree:
1. Prim's Algorithm
2. Kruskal Algorithm
Prims Algorithm computes the minimum spanning tree by including appropriate vertex and thus one edge into existing partially constructed tree in successive stages. The time complexity of the Prim’s Algorithm is O((V+E)logV).
Kruskal Algorithm computes the minimum spanning tree by adding edges one by one into a growing spanning tree. Initially from the graph G, consider a forest of all the vertices without any edge.
1. Sort all the edges in ascending order to their costs.
2. Include the edge with minimum cost into the forest if it does not form a cycle in the partially constructed tree.
3. Repeat step (2) until no edge can be added to the tree.
-------------GRAPHS-----------------
28. What is a Graph?
-> A graph is a pair of sets (V,E), where V is the sets of vertices and E is the set of edges connecting the pair of vertices.
29. What is a Directed and Undirected Graph?
->A graph is directed if each edge of graph has a direction between vertices. A graph is undirected if there are no direction between vertices.
30. What is a Connected Graph?
-> A undirected graph is connected if there is a path from every vertex to every other vertex. A directed graph with this property is called strongly connected.
31. What is a Complete Graph?
-> A complete graph is a graph in which every vertex is connected to every other vertex. That means each vertex's degree in undirected graph is n-1.
32. What is a Acyclic Graph?
->An acyclic graph is a graph which does not have cycles.
33. How are graph represented?
-> A graph can be represented in two forms 'Adjacency matrix' and 'Adjacency list'. Adjacency matrix is a two dimensional arrays where for each edge, (u,v) A[u,v] = true otherwise it will be false. The space complexity to represent a graph using this is O(|V|2).