#include
#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;
}
Time Complexity O(N)
Space Complexity O(1)
Run Here http://ideone.com/DWMmM