Sort And Searching Question: Download Questions PDF
What is Binary Search Tree and explain its time complexity?
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)).
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 Question | Next Question |
| What is Mergesort and Hashtable? | How to sort 1 million floating point numbers? |