On 30 July 2010 02:59, Priyanka Chatterjee <dona.1...@gmail.com> wrote:
> Algo: 1. find height of tree
> 2. do level order traversal
> i> at each level store the address of each tree node in the
> data part of a linked node and form linked list of the nodes
> ii> store the header of a linked list at a certain level in an
> array
> 3. return array.// gives final structure
>
>
> complexity - T(n) =O(n)
> S(n)=O(h+n ) //h=height of tree
>
> //CODE
>
> //tree structure
> struct node {
> int data;
> struct node * left, *right};
>
> // linked list structure
> struct linkNode{
> struct node * data;
> struct linkNode * next;
> }
>
> struct linkNode** func(struct node * root){
>
> struct linkNode ** array;
>
> int i, h=height(root);
> for(i=1;i<=h;i++)
> array[i-1]=levelOrderTraversal(root, i);
>
> return array;// final tree structure
> }
>
> //max height of tree
> int height(struct node *root){
> int hL=height(root->left);
> int hR=height(root->right);
> return 1+ HR>HL?HR:HL;
> }
>
>
>
> struct nodelink* levelOrderTraversal(struct node*root, int level){
> if(root==NULL) return NULL;
>
> if (level==1)
> return createLinkNode(root); // create a node of a singly l
>
>
> struct LinkNode *ptr;
> if(level>1){
> struct nodeLink * ptr1, *ptr2;
> ptr1=levelOrderTraversal(root->left,level-1);
> ptr2=levelOrderTraversal(root->right,level-1);
>
if(ptr1==NULL && ptr2==NULL) return NULL;
if(ptr1==NULL) return ptr2;
if(ptr2==NULL) return ptr1;
ptr1->next=ptr2;
return ptr2;
> }
>
> }
>
>
> struct linkNode * createLinkNode(struct node * root){
>
> struct linkNode* newNode=(struct linkNode*) malloc(sizeof(struct
> linkNode));
>
> newNode->data=root;
>
> newNode->next=NULL;
>
> }
>
>
>
> --
> Thanks & Regards,
> Priyanka Chatterjee
> Final Year Undergraduate Student,
> Computer Science & Engineering,
> National Institute Of Technology,Durgapur
> India
> http://priyanka-nit.blogspot.com/
>
--
Thanks & Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science & Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
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.
