CareerCup

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)).

In a tree, this looks like :

6
				     /	     \
				   2	       20
			        /      \      /     \
			      1      4   10   35

The reason 35 is the worst time complexity is because we had to traverse to the very last tier of the tree to find it. The worst time complexity of the binary search is log(n) because in this example, n = 7 elements and log(7) ceils up to 3. 3 comparisons, and thus the more most time it would take for this example to complete its search.

Hope you can explain what a BST is. It is a binary tree ie. each node has at most two child nodes. And the other criteria are that the left child is less than or equal to the root node value and the right child is greater than the root node in value - for each node.
Since it is not balanced, the time complexities will be following for worst case:
Lookup/Search = O(n)
Insertion = O(n)
Deletion = O(n)
You can also mention that the worst case occurs when all nodes are inserted on only one side of previous nodes - ie. they become more like a linked list.

I can explain binary tree in O(1) time.

DSs have no time comp.
Only operations do.

Refer to a book no need for a thread