# Data Structure Interview Questions | Page 3

##### Question 21:What are the applications where tree data structure can be used?

Some of the real world applications where tree data structure is used is listed below:

• Most XML/Markup parsers use trees. For example Apache Xerces, Xalan XSLT parser.
• PDF is a tree-based format.
• Heuristic search uses tree-based structure for storing training related data. Cor example: Chess Game
• File System uses tree structure to store files and directories.
• Lexical Parsing
##### Question 22:When you should use binary search algorithm?

You should use binary search algorithm when the given list/array is in sorted order.

##### Question 23:What is the difference between Singly Linked List and Doubly Linked List?

Singly Linked List: Singly Linked list is one of the easiest implementation of Linked list which comprises of sequence of nodes and each node comprises of data and address to another node as shown below

Singly linked list allows you to traverse through one way. One of the major advantages of singly linked list over doubly linked list is that it uses less memory.

Doubly Lined List: In Doubly linked list, a node has three fields i.e data element, reference to previous node and reference to next node, which provides it capability to traverse in the forward direction as well as backward direction.

##### Question 24:What is the worst case time complexity of Bubble sort algorithm?

The worst case occurs when the given list of elements is sorted but in descending order.

In this case,  time complexity of bubble sort will be, Big Oh = n + n - 1 + n - 2 ... + 1 = (n*(n + 1))/2 = O(n^2)

##### Question 25:What is the best case time complexity of Bubble sort Algorithm?

The best case occurs when the given list of elements is already sorted in ascending order and sorting was intended for ascending order or vice-versa.

In this case, there will be no swapping and iteration will be done for only once for n elements. Hence the best case time complexity of bubble sort will be O(n)

##### Question 26:What is the best case, average case and worst case time complexity of Heap sort?

The best case, average case and worst case time complexity of Heap sort is listed below:

 Best Case Average Case Worst Case Heap Sort O(nlogn) O(nlogn) O(nlogn)
##### Question 27:What is the best case, average case and worst case time complexity of Merge sort?

The best case, average case and worst case time complexity of Merge sort is listed below:

 Best Case Average Case Worst Case Merge Sort O(nlogn) O(nlogn) O(nlogn)
##### Question 28:What is the worst case time complexity of Quick sort?

In quick sort, we pick an element called the pivot in each step and re-arrange the array in such a way that all elements less than the pivot now appear to the left of the pivot, and all elements larger than the pivot appear on the right side of the pivot. In all subsequent iterations of the sorting algorithm, the position of this pivot will remain unchanged, because it has been put in its correct place.

The worst case of quicksort, which happens when the pivot we picked turns out to be the least element of the array to be sorted, in every step (i.e. in every recursive call). A similar situation will also occur if the pivot happens to be the largest element of the array to be sorted. In such case the time complexity of quick sort will be O(n2)

##### Question 29:What is the best case, average case and worst case time complexity of Quick sort?

The best case, average case and worst case time complexity of Quick sort is listed below:

 Best Case Average Case Worst Case Quick Sort O(nlogn) O(nlogn) O(n2)
##### Question 30:What is the best case, average case and worst case time complexity of Selection sort?

The best case, average case and worst case time complexity of Selection sort is listed below:

 Best Case Average Case Worst Case Selection Sort O(n2) O(n2) O(n2)