#include <stdio.h>

#include <stdlib.h>

/*Data structures*/

typedef struct TreeNode

{

struct TreeNode *left, *right, *sibling;

int data;

}TreeNode;

typedef TreeNode * Tree;

/*

For each level there will be one list node, which has prev pointer pointing to TreeNode for which sibling has to populate in that level

*/

typedef struct ListNode

{

TreeNode *prev;

struct ListNode *next;

}ListNode;

typedef ListNode *List;

/*End of data structures*/

/*

*Function which populates siblings

*/

void PopulateSibling(Tree t, ListNode *prevLevel) //preorder traversal

{

if(t == NULL)

return;

ListNode *node = prevLevel->next;

if(node == NULL) //allocate node to the current level, if not yet allocated

{

node = calloc(sizeof(ListNode), 1);

prevLevel->next = node;

}

else if(node->prev) //if prev is there in this level, populate sibling

node->prev->sibling = t->left ? t->left : t->right;

if(t->left)

{

if(t->right) //sibling of left is right if there, else populate node->prev

{

node->prev = t->left->sibling = t->right;

}

else

node->prev = t->left;

PopulateSibling(t->left, node);

}

PopulateSibling(t->right, node);

}

/*Utilities*/

inline TreeNode * makeTreeNode(int data)

{

TreeNode *n = calloc(sizeof(TreeNode), 1);

n->data = data;

return n;

}

/* prints if left most is the first node in sibling list*/

inline void printSibling(Tree t)

{

TreeNode *sibling;

while(t)

{

printf("%d ", t->data);

sibling = t->sibling;

while(sibling)

{

printf("%d ", sibling->data);

sibling = sibling->sibling;

}

printf("\n");

t = t->left;

}

}

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->left->left = makeTreeNode(70);

t->right->right->left = makeTreeNode(60);

t->right->right->right = makeTreeNode(160);

/*Empty List head*/

ListNode head = {NULL, 0};

PopulateSibling(t, &head);

printSibling(t);

return 0;

}

Advertisements