the best approach to it is to build a balanced tree from bottom to up rather
than top to bottom.
On 12 May 2010 22:47, divya jain <sweetdivya....@gmail.com> wrote:
> thanks a lot to all for their replies..
>
>
> On 9 May 2010 11:23, rahul rai <raikra...@gmail.com> wrote:
>
>> can anyone give me links to more educative and active groups like
>> algogeeks
>>
>> On Sun, May 9, 2010 at 2:11 AM, Arun prasath
>> <aruntendulkar2...@gmail.com> wrote:
>> > This does not create a balanced tree but ensures that every element in
>> the
>> > tree is accessible by lg(n) time.
>> >
>> > Time : Complexity O(n)
>> >
>> >
>> > [a...@91blore-srv1 ~]$ cat recursion.c
>> > #include <stdlib.h>
>> > #include<unistd.h>
>> > #include <stdio.h>
>> > #define TEST2
>> > #ifdef TEST1
>> > int arr[] = { 1,2,3,4,5,6,7};
>> > int max_elems = sizeof(arr)/sizeof(arr[0]);
>> > #endif
>> >
>> > #ifdef TEST2
>> > int arr[] = { 1,2,3,4,5};
>> > int max_elems = sizeof(arr)/sizeof(arr[0]);
>> > #endif
>> >
>> > #ifdef TEST3
>> > int arr[] = { 1,2,3,4,5,6,7,8};
>> > int max_elems = sizeof(arr)/sizeof(arr[0]);
>> > #endif
>> >
>> > #define LIST_EMPTY -1
>> >
>> > struct tree {
>> > int data;
>> > struct tree * left,* right;
>> > };
>> >
>> > struct tree* function( int , int);
>> > void print_inorder( struct tree *);
>> >
>> > int return_next_from_list(void)
>> > {
>> > static int nxt_elem = 0;
>> > if(nxt_elem < max_elems)
>> > return arr[nxt_elem++];
>> >
>> > return LIST_EMPTY;// empty condition
>> > }
>> > int main()
>> > {
>> > unsigned int x = max_elems;
>> > struct tree* head;
>> > while( x & (x - 1) ) {
>> > x = x & (x - 1) ;
>> > }
>> >
>> > head = function(0, x);
>> > print_inorder(head);
>> > free(head);
>> > return 0;
>> > }
>> > struct tree* function(int mid, int i)
>> > {
>> > int val = mid + i ;
>> > if (val & 1) {
>> > struct tree * leaf = malloc( sizeof(struct tree) );
>> > leaf->left = leaf->right = NULL;
>> > leaf->data = return_next_from_list();
>> > if(leaf->data == LIST_EMPTY) {
>> > free(leaf);
>> > return NULL;
>> > }
>> > return leaf;
>> > }
>> > struct tree *non_leaf = malloc( sizeof(struct tree) ) ;
>> >
>> > non_leaf->left = function( mid, i/2);
>> > non_leaf->data = return_next_from_list();
>> > if (non_leaf->data == LIST_EMPTY) {
>> > struct tree *tmp = non_leaf->left;
>> > free(non_leaf);
>> > return tmp;
>> > }
>> > non_leaf->right = function( mid+i, i/2);
>> > return non_leaf;
>> > }
>> > void print_inorder( struct tree* root)
>> > {
>> > struct tree * trav = root;
>> > if (!trav) {
>> > return;
>> > }
>> > print_inorder(trav->left);
>> > if(trav->left)
>> > free(trav->left);
>> > printf("{%d}", trav->data);
>> > print_inorder(trav->right);
>> > if(trav->right)
>> > free(trav->right);
>> >
>> > }
>> > [a...@91blore-srv1 ~]$
>> >
>> >
>> > On Sun, May 2, 2010 at 6:38 PM, divya <sweetdivya....@gmail.com> wrote:
>> >>
>> >> u are given a sorted lnked list construct a balanced binary search
>> >> tree from it.
>> >>
>> >> --
>> >> You received this message because you are subscribed to the Google
>> Groups
>> >> "Algorithm Geeks" group.
>> >> To post to this group, send email to algoge...@googlegroups.com.
>> >> To unsubscribe from this group, send email to
>> >> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> >> For more options, visit this group at
>> >> http://groups.google.com/group/algogeeks?hl=en.
>> >>
>> >
>> > --
>> > You received this message because you are subscribed to the Google
>> Groups
>> > "Algorithm Geeks" group.
>> > To post to this group, send email to algoge...@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> > For more options, visit this group at
>> > http://groups.google.com/group/algogeeks?hl=en.
>> >
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
