Binary tree to Single Linked List containg sum of all nodes at the same level

Problem
#include <stdio.h>
#include <stdlib.h>

#define max(a,b) (a) > (b) ? (a) : (b)

/*Data structures*/
typedef struct TreeNode
{
struct TreeNode *left, *right;
int data;
}TreeNode;

typedef TreeNode * Tree;

typedef struct ListNode
{
struct ListNode *next;
int data;

}ListNode;

typedef ListNode *List;

/*End of data structures*/

/*
*Function which collapses all the nodes at a level in a binary tree to one Listnode
*/
void BinTreeToLinkedList(Tree t, ListNode *parent)
{
if(t == NULL)
return;

ListNode *node = parent->next;

if(node == NULL)
{
node = calloc(sizeof(ListNode), 1);
parent->next = node;
}

node->data += t->data;

BinTreeToLinkedList(t->left, node);
BinTreeToLinkedList(t->right, node);
}


/*Utilities*/

inline TreeNode * makeTreeNode(int data)
{
TreeNode *n = calloc(sizeof(TreeNode), 1);
n->data = data;

return n;
}

inline void printList(List l)
{
while(l)
{
printf("%d ", l->data);
l = l->next;
}
printf("\n");
}

int main()
{
/*level 0*/
Tree t = makeTreeNode(10);

/*level 1*/
t->left = makeTreeNode(20);
t->right = makeTreeNode(30);


/*level 2*/
t->left->left = makeTreeNode(40);
t->left->right = makeTreeNode(70);
t->right->left = makeTreeNode(50);
t->right->right = makeTreeNode(60);

/*level 3*/
t->left->right->left = makeTreeNode(70);
t->right->right->left = makeTreeNode(60);
t->right->right->right = makeTreeNode(160);

/*Empty List head*/
ListNode head = {NULL, 0};

/*Convert tree to list*/
BinTreeToLinkedList(t, &head);

/*print list*/
printList(head.next);


return 0;
}
Advertisements

One thought on “Binary tree to Single Linked List containg sum of all nodes at the same level

  1. Nice Solution…but some corrections:-1) node = calloc(sizeof(ListNode), 1);correction:-node = (ListNode*)calloc(sizeof(ListNode), 1);2) TreeNode *n = calloc(sizeof(TreeNode), 1);correction:-TreeNode *n = (TreeNode*)calloc(sizeof(TreeNode), 1);

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s