Sort And Searching Interview Question:

What is Binary Search Tree and explain its time complexity?

Submitted by: Administrator

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)).
Submitted by: Administrator