The Gateway to Computer Science Excellence

+3 votes

Consider the following algorithm to build a balanced search tree from a sorted sequence.

* Make the mid-point of the sequence the root of the tree

* Recursively construct balanced search trees from elements to the left and right of the midpoint and make these the left and right subtrees of the root.

A. What is the complexity of this procedure where the sorted sequence is a sorted list?

1- O(n)

2- O(n log n)

3- O(n2)

4- Depends on the contents of the original sequence.

B. What is the complexity of this procedure where the sorted sequence is a sorted array?

1- O(n)

2- O(n log n)

3- O(n2)

4- Depends on the contents of the original sequence

* Make the mid-point of the sequence the root of the tree

* Recursively construct balanced search trees from elements to the left and right of the midpoint and make these the left and right subtrees of the root.

A. What is the complexity of this procedure where the sorted sequence is a sorted list?

1- O(n)

2- O(n log n)

3- O(n2)

4- Depends on the contents of the original sequence.

B. What is the complexity of this procedure where the sorted sequence is a sorted array?

1- O(n)

2- O(n log n)

3- O(n2)

4- Depends on the contents of the original sequence

0

even the linked list ? ... should not we traverse the list to get the middle pointer ?

total recursive call will be = $O(n)$ ok !

But I think in Linked list to get to the middle we have an overhead of $O(n)$

=> $O(n\log n)$

correct if wrong

total recursive call will be = $O(n)$ ok !

But I think in Linked list to get to the middle we have an overhead of $O(n)$

=> $O(n\log n)$

correct if wrong

+4 votes

Best answer

**A). If we see the first basic approach , then we can find the middle element in O(n) .**

**We are using here top - down approach i.e , Recursively designing BST from root to leaves .**

List middle element can be found in O(n) which is the root .

Then, similarly , left subtree and right subtree mid element (root) can be found in O(n) time .

root cost = n

Left + right subtree cost = 2n

........................

Total cost = n + 2n + 4n + 8n + .......... = O(n)

and the height is O(h) = O(log n)

Hence, total complexity ==> O(n logn) .

**Now, we use 2nd approach , which can reduce this complexity to O(n) .**

**Apply both top down and bottom up approach,**

First finding middle element takes O(n) time .

Now, traverse along first element to root which has n/2 elements in the path as the tree is balanced , which takes O(n). This follows bottom up approach .

And, similarly, making root element as head pointer , make a BST (right subtree ) just by traversing the elements. This follows top down approach .

**Hence , total time ==> O(n + n + n) = O(n) . This includes finding the mid element and traversing from leaf to root and then traverse from root to leaf .**

**B). Simple procedure , access all the elements in O(n) .**

+1

@kapil ? This procedure ? http://articles.leetcode.com/convert-sorted-list-to-balanced-binary

In this case recurrence relation for time complexity coming out to be :

recursive prcedure call : $T(n) = 2T\left ( \frac{n}{2} \right ) + O(1)$ => $T(n) = O(n)$

and for elements couting purpose $O(n)$ prior to the recursive call.

Total = $O(n)$

+1

yes, this link is also saying same thing .

I read these methods from a java book earlier , which says

1). sorted list to BST ==> O(n) .

2. sorted DLL to BST ==> O(n) .

And for such questions based on trees, always apply bottom up approach along with top down approach .

I read these methods from a java book earlier , which says

1). sorted list to BST ==> O(n) .

2. sorted DLL to BST ==> O(n) .

And for such questions based on trees, always apply bottom up approach along with top down approach .

0

Thanks !

Since we are calling the recursive function from a large span (say, start = 0 and end = n-1) and going down recursively calling itself again with smaller range. And finally if we hit a certain node in the linked list, we form a node (allocate a memory for the tree node with linked list node.data ) for the our tree. Although we are pluging linked list nodes in the tree from list start pointer, actual recursive calls are coming from top.

I think this approach is top down. other example : f(n) = f(n-1) + f(n-2) fibonacci recursive calling from n : which is top down. Above link, and many other sources are saying it as bottom up.

Could you please refer code for the bottom up approach ?

Since we are calling the recursive function from a large span (say, start = 0 and end = n-1) and going down recursively calling itself again with smaller range. And finally if we hit a certain node in the linked list, we form a node (allocate a memory for the tree node with linked list node.data ) for the our tree. Although we are pluging linked list nodes in the tree from list start pointer, actual recursive calls are coming from top.

I think this approach is top down. other example : f(n) = f(n-1) + f(n-2) fibonacci recursive calling from n : which is top down. Above link, and many other sources are saying it as bottom up.

Could you please refer code for the bottom up approach ?

+1

Yes, if we are calling from N, then it is top down . For bottom up, it must be using **tabulation technique**.

0

0

Your link says it all,

First make recursive calls until we get NULL.

Now , start from NULL , find parent , then right child by ` `

`parent->right = sortedListToBST(list, mid+1, end);`

`Hence, whole think works like left child -> parent -> right child .`

`I thought like this for BU .`

`I dont have my code as now now .`

0

eventually constructing from bottom ! ok ! fine !, but did we gave command from bottom ? no. We gave from entire span (start =0 ,end=n-1).

In fibonacci recursive also recursion starts from N , bounce back from f(0) or f(1) only and internally added to form subsolutions f(2),f(3).etc...

That's what we call Top down, according to me.

In fibonacci recursive also recursion starts from N , bounce back from f(0) or f(1) only and internally added to form subsolutions f(2),f(3).etc...

That's what we call Top down, according to me.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,306 answers

198,314 comments

105,011 users