Sort And Searching Question:

Download Job Interview Questions and Answers PDF

What is Binary Search Tree and explain its time complexity?

Sort And Searching Interview Question
Sort And Searching Interview Question

Answer:

Traverse: O(n). Coz it would be visiting all the nodes once.
Search : O(log n)
Insert : O(log n)
Delete : O(log n)

Binary Search is a searching algorithm that is used on a certain data structure (ordered array) to find a if an element is within the array through a divide a conquer technique that takes the middle value of the array and compares it to the value in question. If the value is less, then compare the value in question to the lower mid-value and if greater, vice versa until you find the value or determine that it is none of the elements within the array. All a Binary Search Tree is a visual concept that allows one to see this divide a conquer technique in an easier way. For example, given : Array A = {1,2,4,6,10,20,35} we ask if the number 35 is there. First you would compare 20 to 6. 20<,>,= 6? Greater than, so compare the mid value of upper range. 35>,<,=20? greater than, compare next greater mid value. 35>,<, = 35 ? Equal. So it has been search with only three comparisons, with the worst time complexity of O(log(n)).

Download Sort And Searching Interview Questions And Answers PDF

Previous QuestionNext Question
What is Mergesort and Hashtable?How to sort 1 million floating point numbers?