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].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
