Populating Siblings in a binary tree

#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

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