Q11: What is a tree data structure?

• The tree is a recursive, non-linear data structure consisting of the set of one or more of the data nodes, in which one node is referred to as the root and the other nodes as the root children.
• The tree hierarchically arranges data.
• A binary tree and its variations are the most widely used tree data structure.
• Some of the applications of trees are:
• Filesystems — files inside folders that are in inturn inside other folders.
• Comments on social media — comments, replies to comments, replies to replies, etc form a tree representation.
• Family trees — parents, grandparents, children, and grandchildren, etc that represent the family hierarchy.

Q12: How can AVL Tree be useful in all the operations as compared to Binary search tree?

Ans:By not allowing it to get bogged down, the AVL Tree regulates the height of the binary search tree. The time required for every operation in the binary height h search tree is O (h). However, if BST is skewed, it may be extended to O(n) (i.e. worst case). If this height is limited to log n, the tree imposes on each operation a higher limit that is O(log n), where n is the number of nodes.

Q13: What is topological sorting in a graph?

Ans:

• Topological sorting is a linear ordering of vertices such that for every directed edge ij, vertex i comes before j in the ordering.
• Topological sorting is only possible for Directed Acyclic Graph (DAG).
• Applications:
• jobs scheduling from the given dependencies among jobs.
• ordering of formula cell evaluation in spreadsheets
• ordering of compilation tasks to be performed in make files,
• data serialization
• resolving symbol dependencies in linkers.
• Topological Sort Code in Java:

// V - total vertices

// visited - boolean array to keep track of visited nodes

// graph - adjacency list.

// Main Topological Sort Function.

void topologicalSort()

{

Stack stack = new Stack();

// Mark all the vertices as not visited

boolean visited[] = new boolean[V];

for (int j = 0; j < V; j++){

visited[j] = false;

}

// Call the util function starting from all vertices one by one

for (int i = 0; i < V; i++)

if (visited[i] == false)

topologicalSortUtil(i, visited, stack);

// Print contents of stack -> result of topological sort

while (stack.empty() == false)

System.out.print(stack.pop() + " ");

}

// A helper function used by topologicalSort

void topologicalSortUtil(int v, boolean visited[],

Stack stack)

{

// Mark the current node as visited.

visited[v] = true;

Integer i;

// Recur for all the vertices adjacent to the current vertex

Iterator it = graph.get(v).iterator();

while (it.hasNext()) {

i = it.next();

if (!visited[i])

topologicalSortUtil(i, visited, stack);

}

// Push current vertex to stack that saves result

stack.push(new Integer(v));

}

Q14: What are the advantages of Binary search over linear search?

Ans:In binary search, comparisons are substantially less than in linear search. On average, a linear search takes O(n) to search a list of n items while O(log n) is used to search for a list of n elements via a binary search.

Q15: How do you search for a target key in a linked list?

Ans:You must sequentially search to discover the target key in a linked list. Each node is crossed and compared to the destination key. If different, the link to the next node follows. This crossing goes on to either identify the target key or to reach the final node.