array and linked list are not the same so all solutions based on array are wrong.
think this way : how to print(or append in a linked list) the binary search tree in the sorted order -- the answer is in-order traversal. you need to do opposite of it here. On May 12, 10:17 am, divya jain <[email protected]> wrote: > thanks a lot to all for their replies.. > > On 9 May 2010 11:23, rahul rai <[email protected]> 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 > > <[email protected]> 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 <[email protected]> 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 [email protected]. > > >> To unsubscribe from this group, send email to > > >> [email protected]<algogeeks%[email protected]> > > . > > >> 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 [email protected]. > > > To unsubscribe from this group, send email to > > > [email protected]<algogeeks%[email protected]> > > . > > > 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 [email protected]. > > To unsubscribe from this group, send email to > > [email protected]<algogeeks%[email protected]> > > . > > 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group > athttp://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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
