CareerCup

Here is my code:

Assuming my node structure is:

struct tree_node
{
	int val;
	tree_node * left;
	tree_node * right;
	tree_node * sib;
};

void siblinglink(tree_node * root)
{
	tree_node * p;
	if(root == NULL)
		return;	
	if(root->right != NULL && root->left != NULL)
		root->right->sib = root->left;
	siblinglink(root->left);
	siblinglink(root->right);
}

For some reason my first reaction was to use a queue and do it non recursive.

Queue q;
q.add(root)
while(!Q.empty())
{
node* top = q.pop();
if (top->right && top->left)
{
// connect rt to left
}
if (top->left)
q.add(top->left)
if (top->right)
q.add(top->right)

}

same complexity in terms of space...we use explict queue here instead of recursion stack

if right child is linked to left sibling, then there will be no right child left in the tree right? thus the right tree should be set as NULL after linking to their left sibling

void linkRtoL(Tree* root)
{
if(!root) return NULL;
if(root->left&root->right)
{ root->left->sib=root->right;
root->right=NULL;
}
linkRtoL(root->left);
linkRtoL(root->sib);

}

I'm unabel to understand why Right child node goes to NULL?pls explain

should use this struct, no sibling pointer. use right pointer as sibling pointer.
struct tree_node {
int val;
tree_node * left;
tree_node * right;
};

Anonymous on January 01, 2009 is right

I think interviewer must expecting that right pointer should be used to point to sibling otherwise this problem becomes very simple.

Here is my solution --- initially function shd be called by passing NULL as sibling value as root has no sibling. and at each subsequent node, remove right pointer and make it to point to sibling of given node. also you will need to store value of actual right subtrees pointer before doing this.

Caller :- covertToLeftSibling(root, NULL);

Function definition-

covertToLeftSibling(Node root, Node sib)
{
Node t= NULL;
if(!root)
return;
       else
       {
           if(root->left && root->right)
           {
                t= root->right; 
                root->right =sib;
                
                 covertToLeftSibling(  t, NULL );        
                 covertToLeftSibling(  root->left, t );        
           }
           else
           {   if(root->left)
               {
                    root->right =sib;
                    covertToLeftSibling(  root->left, NULL );        
               }
               else
               {
                   if(root->right)
                   {
                                root->left= root->right;   
                                root->right =sib;
                   }
                   else
                   {
                                   root->right =sib;
                   }
                   
               }
               
           }
    
       }                         
}

void connect(Node* p) {
if (!p) return;
if (p->leftChild)
p->leftChild->nextRight = p->rightChild;
if (p->rightChild)
p->rightChild->nextRight = (p->nextRight) ? p->nextRight->leftChild : NULL;
connect(p->leftChild);
connect(p->rightChild);
}

Correction in the above solution!!!

void connect(Node* p) {

if (!p) return;
if (p->rightChild)
p->rightChild->nextLeft = p->leftChild;
if (p->leftChild)
p->leftChild->nextLeft = (p->nextLeft) ? p->nextLeft->rightChild : NULL;

connect(p->rightChild);
connect(p->leftChild);
}

hats off to harsh great job buddy :)

An easier solution for Harsh's question is

void LinkSiblings(Node * root)
{
if (!root)
return;

LinkSiblings(root->left);
LinkSiblings(root->right);

if (root->left)
{
root->left->right = root->right;
root->right = NULL;
}
}

An easier solution for Harsh's question is:

void LinkSiblings(Node * root)
{
	if (!root)
		return;

	LinkSiblings(root->left);
	LinkSiblings(root->right);

	if (root->left)
	{
		root->left->right = root->right;
		root->right = NULL;
	}
}