CareerCup

BST * siblingsTransform(BST *root)
{
if(root == NULL)
return NULL;
siblingsTransform(root->left);
siblingsTransform(root->right);
if(root->left !=NULL)
{
root->left ->right = root->right;
root->right = NULL;
}
else
{
root->left = root->right;
}
return root;
}

So basically you get to the right child by following the right pointer (sibling) of the left child? (or vice versa). Can you please explain more clearly?

Yes.

isnt that similar to printing the tree level wise? am i missing something here?

Nope......you should transform in such a way that left child of a node should point to its sibling (i.e. right child) and parent node's right should be null. You should not reconstruct the tree but make use of the current node structure.

LC-RS Tree : en.wikipedia.org/wiki/Left-child_right-sibling_binary_tree

Using PostOrder Traversal
Complexity : o(N)

//assuming that every node has one left child, in case it has only one child

Convert(Node *head){
if(head->left == NULL)
return;
Convert(head->left);
(head->left)->right = Convert(head->right);
head->right = NULL;
}

void transform(node *root){
node *p = root->left;
node *q = root->right;
if(p) transform(p);
if(q) transform(q);
if(p) p->right = q;
else root->left = q;
root->right = NULL;
}