# Data Structure Interview Questions | Page 4

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

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

 Best Case Average Case Worst Case Insertion Sort O(n) O(n2) O(n2)
##### Question 32:When insertion sort will have best case time complexity?

The best case in insertion sort algorithm will occur when the given list of element is in sorted order. During each iteration, the first remaining element of the input is only compared with the elements of the sorted subsection of the array. Hence, the best case time complexity of insertion sort is O(n)

##### Question 33:How will you check whether given binary tree is balanced or not?

A binary tree is said to be balanced if the difference between the depth of the left and right subtrees of every node is not greater than one.

For example:-

In above example, the maximum difference between the depth of left subtree and right subtree of any node is not greater than 1. Hence above tree is balanced binary tree.

##### Question 34:Given a string, you have to reverse the words inside it. Example "This is cool question" –> "question cool is This". Design an algorithm and implement it. You are not allowed to use String.Split() method.

You can achieve the solution using below steps:

1. Reverse whole the string char by char you will get noitseuq looc si sihT
2. Reverse again the characters in each word you will get question cool is This
##### Question 35:What is difference between height and depth of tree?

Depth: The depth of any node is the number of edges from the node to the tree's root node. A root node will have a depth of 0.

Height: The height of any node is the number of edges on the longest downward path between that node and a leaf. A leaf node will have a height of 0.

##### Question 36:For a given tree of node "n", what will be the number of possible trees that can be formed?

The possible number of trees that can be formed of node "n" = 2n - n

##### Question 37:Let S be a set of n integers. One can create a data structure for S so that determining whether an integer x belongs to S can be performed in O(1) time in the worst case. What will be the data structure?

Using Perfect Hashing the above requirement can be achieved.

Share interview questions