Binary Search tree

Question

Consider an array with ‘n’ numbers, let “T” be time complexity for finding a number appeared maximum number of times in an array. Using Binary Search Tree data structure the T will be

A. O(log n)

B. O(n)

C. O(n logn)

D. O(n2)

Answer 1

Suppose number is given x we need to find it appears maximum number of times or not i.e more than n/2 times or not.

Array is not give in sorted order So use Inoredr Traversal and sort it O(n). Logic over here is find the index of x into the array by using Binary search O(logn) time suppose index is i. Now check element at (i + n/2) =O(1) also x if yes than it is maximal element else not. 

If Array has given in sorted order than Time complexity will be O(logn) but Here  O(n). 

Assuming BST available. If not available than O(nlogn) should be the ans 

--------------------------------------------------------------------------------------------------------------------------------------------------------------

Same procedure apply for when x is not given .

Step1: Build BST= O(nlogn)  = Sort the array + Than build BST  = O( nlogn + n )

Step2. Each Element search into BST and check it's index i and i+ (n/2)^th element = O(nlogn)

So Time complexity = O(nlogn)

----------------------------------------------------------------------------------------------------------------------------------------------------------------

Improvement Welcomes :

Comments

But TC of building a BST is O(n log n) right?

---

@Gabbar

Question says only array not sorted array, rt ?

With only array, array is first sorted then can be made BST, but here augmented BST with extra space is needed, so TC = O(NLogN + N)

---

so its O(n log n) right?

Answer 2

Using augmentation in binary search tree , we can simplify this problem..

So what we do is we modify in insertion method..First prior to insertion if we find the key already is present in BST then we increase the count field of the concerned node..

Else we insert the node and make count of it = 1 in the augmented BST..

So to find maximum frequency character we do inorder traversal of this BST and check the count value and update the max value and character as and when required..

Hence the complexity is O(n)..Hence B) should be correct answer..

Comments

@Habib Just one doubt : We are given array of numbers [may be sorted not always] so to apply inorder traversal first we need to build the BST so T.C can never be less than nlogn right ?

Time for max : Build BSt with augmentation + Inorder Traversal = O(nlogn) + O(n) ==> O(nlogn)

---

Sir, for checking whether the key is already present in BST would take log n time right? and doing this for n items would take n log n right?

---

Here my point is : We can make the binary search tree augmented as I described by taking care in insertion itself so that we can solve the problem of finding frequent element in O(n) time..We take care of that fact in insertion itself..

---

Sir, so finding the element with max frequency element will take O(n) if we don't consider insertion cost right?

If so, why shouldn't we consider it?

---

@Gate Mission 1, A tree traversal would take only O(n) because all tree tranversals are depth first traversals, tc of dfs is O(n+m) $\simeq$ O(n). In another way we visit all the n nodes, so O(n).

---

@habib your approach is correct all is you are not thinking of worst case of BST on each insert if you first find nd then decide whether to insert or not --> Aren't you going to include time for "finding" --> consider skew bst. only finding time leads to triangle numbers.

@nitish don't complicate that much, tree traversal means exploring edges and in any traversal you can traverse an edges at most twice (once exploring and once backtracking) and in tree there are n-1 edges so T.C is always O(n).

---

Yeah @Gate Mission 1 that is what I meant.

What I don't understand is why we should ignore insertion cost?