CareerCup

// call function by (root, null) as for parent node its not having any sibling
sibling(node* root, node* sib)
{   if(root==null)
        return;
    root->sibling=sib;
    sibling(root->left,root->right);
    sibling(root->right,null)
    //as right child of all nodes do not have sibling in binary tree
    
}

Considering the fact that the tree has a left pointer, right pointer and another extra pointer say 'next' which would help the leaf nodes to be linked and form a linked list. I guess this works fine for all the cases. Do check.

The node returned will be the head of the list. Traverse the tree in preorder and collect the leaf nodes and link them.


struct node* returnlisthead(struct node* headref)
{
struct node* left;
struct node* right;
if(headref==NULL)
return NULL;
else if(headref->left==NULL && headref->right==NULL)
return headref;
else
{
left= returnlisthead(headref->left);
right=returnlisthead(headref->right);
if(left!=NULL)
left->next=right;
}
if(left!=NULL)
return left;
else
return right;
}

struct node {
int value;
node* left;
node* right;
node* sibling;
}


void ConnectSiblings(node* pTree) {
Assert (pTree!=null);
Vector<node*> tmp = new Vector<node*);
tmp.Clear();
tmp.Push_back(pTree);
while (tmp.size()!=0) {
int count = tmp.size();
for(int i=0; i<=count-2; i++) {
tmp[i]->sibling = tmp[i+1];
if(tmp[i]->left) {
tmp.push_back(tmp[i]->left);
}
if(tmp[i]->right) {
tmp.push_back(tmp[i]->right);
}
}
tmp[count-1].sibling = null;
if(tmp[count-1].left) {
tmp.push_back(tmp[count-1].left);
}
if(tmp[count-1].right) {
tmp.push_back(tmp[count-1].right);
}
for(i=0; i<=count-1; i++) {
tmp.remove[0];
}
}
}

use BFS if all nodes (i.e., they need not be siblings) at the same level should be connected as linked list from left to right. if the binary tree is height balanced, then the max space required for the queue would be 2^h. traversal would take O(n) time.

if only the siblings need to be linked, then use post/pre-order traversal. traversal would take O(n) time. if the binary tree is height balanced, then the growth of stack space would be O(lg n).

following code would work:
void siblingpointer(node *p)
{
if(p==NULL)
return;
siblinpointer(p->left);
siblingpointer(p->right);
if(p->left)
p->left->sibling=p->right;
if(p->right)
p->right->sibling=p->left;
}

1
/\
2 3
/\ /\
4 5 6 7

if such a tree is given 2's sibling should point to 3 4's to 5, 5's to 6, 6's to 7
The above code wont work

the above code is wrong, what we are supposed to do is as mentioned by Idea. the code givne is not even partially right? the right pointer sibling is wrongly assigned. One way we can do is have a function that gives the pointers to all the nodes of a given level. Now modify the above code and plug this method and do the sibling pointing from left to right in a given level at one shot. thats it...now it all boil downs to writing the code for writing this simple function that gives you the pointers to all the nodes. for this we can have an iterator in the logic and calling next() will give the next node in the level and NULL will mark the end. does this sound ok?

Do a level order traversal ... It traverses
1
/\
2 3
/\ /\
4 5 6 7

as 1,2,3,4,5,6,7 ... Then siblings can be set as mentioned ..

if(p->left)
p->left->sibling=p->right;
if(p->right)
p->right->sibling=p->left;

The program should be something like this ... correct me if I'am wrong.

void SetSiblings(node *root)
{
// Assuming the queue impelementation is
// outside the scope of the problem
queue *q = new queue();

q->insert(root);
while (!q->isEmpty())
{
node *trav = q->remove();
if ((trav->left) && (trav->right))
{
trav->left->sibling = trav->right;
trav->right->sibling = trav->left;
}
if (trav->left) q->insert(trav->left);
if (trav->right) q->insert(trav->right);
}
}

void adjustSiblingPtrs( Node* root )
{
	if ( root == NULL )
	{
		return;
	}
	if ( root->left != NULL )
	{
		root->left->sibling = root->right;
	}
	if ( root->right != NULL )
	{
		root->right->sibling = root->left;
	}
	adjustSiblingPtrs( root->left );
	adjustSiblingPtrs( root->right );
}

Do a Breadth First Search, keeping a marker to mark the end of a 'level'.

Normally breadth first search traversal uses a queue (as opposed to a depth first search which uses a stack).

Here is some pseudo-code which uses a NULL pointer as the marker.

I think this works, but who knows.

void SetSiblings(Node *root)
{
    if (!root) return;
    
    Node *prev = NULL; // This stores the left sibling of the dequed node.

    Queue <Node *> q = new Queue<Node *>();

    q.Enque(root);
    q.Enque(NULL); //  Queue the marker.
    
    while (! q.IsEmpty())
    {
        Node *cur = q.Deque();
    
        if (cur == NULL) // We hit the marker
        {
            if (q.IsEmpty()) // We are done.
            {
                break;
            }
            // Enque the marker.
            q.Enque(NULL);
            // Reset prev.
            // If we don't do this, we can form a linked list of nodes
            // which would give a bfs of tree.
            prev = NULL;
        }
  
        if (prev != NULL) 
        {
            prev->sibling = cur;
        }
        
        prev = cur;
   
        // Enque children.
        q.Enque(cur->left);
        q.Enque(cur->right);
    }
    
    delete q;
}

According to your description of the problem, this code should do it:

void link(node* root) {
    queue<node*> q, neighbours;
    int index = 0, level = 1;
    node* cur = NULL;

    q.push(root);

    do {
        if ((1 << level) == index + 1) {
            ++level;
            while (!neighbours.empty()) {
                cur = neighbours.front();
                neighbours.pop();
                cur->adj = neighbours.front();
            }
        }

        neighbours.push(q.front());
        if (q.front()->left) q.push(q.front()->left);
        if (q.front()->right) q.push(q.front()->right);
        q.pop();
        ++index;
    } while (!q.empty());
}

Based on LoLer's solution:

void link(node* root) {
    queue<node*> q;
    node* cur = root;

    q.push(root);
    q.push(NULL);

    do {
        cur = q.front();
        q.pop();
        
        if (cur) {
            cur->adj = q.front();
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        } else {
            if(q.front() == NULL) return;
            q.push(NULL);
        }
    } while (!q.empty());
}

void link(node* root) {
    queue<node*> q, neighbours;
    int index = 0, level = 1;
    node* cur = NULL;
    q.push(root);
    do {
        if ((1 << level) == index + 1) {
            ++level;
            while (!neighbours.empty()) {
                cur = neighbours.front();
                neighbours.pop();
                cur->adj = neighbours.front();
            }
        }
        neighbours.push(q.front());
        if (q.front()->left) q.push(q.front()->left);
        if (q.front()->right) q.push(q.front()->right);
        q.pop();
        ++index;
    } while (!q.empty());
}

//assuming cur->next = NULL

bool JoinTree(node *head)
{
if(head == NULL )
{
return false;
}

node *cur = head;
node *tail = head;

while(cur)
{
if(cur->left)
{
tail->next = cur->left;
tail = tail->next;
}

if(cur->right)
{
tail->next = cur->right;
tail = tail->next;
}

cur = cur->next;
}

return true;
}

#include<vector>
typedef int Data;


typedef struct tree_node *tree_pointer;
typedef struct tree_node
{
tree_pointer left;
tree_pointer right;
tree_pointer sibling;
Data data;
};

tree_pointer generateTree();
void freeTree(tree_pointer ptr);
void printTree(tree_pointer ptr);
void updateSiblings(std::vector<tree_pointer> &vecPtr);




#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <iostream>
#include <cstdlib>
#include "llofsibling.h"

using namespace std;

int main(int argc, char *argv[])
{
tree_pointer ptr = generateTree();
printTree(ptr);

std::vector<tree_pointer> vecPtr;
vecPtr.push_back(ptr);

cout << "Update Sibling" << std::endl;
updateSiblings(vecPtr);
vecPtr.clear();

cout << std::endl;
printTree(ptr);

freeTree(ptr);
return EXIT_SUCCESS;
}

tree_pointer generateTree()
{
tree_pointer ptr = (tree_pointer)calloc(1, sizeof(tree_node));
ptr->data = 1;
ptr->left = (tree_pointer)calloc(1, sizeof(tree_node));
ptr->left->data = 2;

ptr->right = (tree_pointer)calloc(1, sizeof(tree_node));
ptr->right->data = 3;

ptr->left->left = (tree_pointer)calloc(1, sizeof(tree_node));
ptr->left->left->data = 4;

ptr->right->left = (tree_pointer)calloc(1, sizeof(tree_node));
ptr->right->left->data = 6;

return ptr;
}

void freeTree(tree_pointer ptr)
{
if(ptr)
{
freeTree(ptr->left);
freeTree(ptr->right);
free(ptr);
}
}

void printTree(tree_pointer ptr)
{
if(ptr)
{
std::cout << (int)ptr << " " << ptr->data << " " << (int)ptr->sibling << std::endl;
printTree(ptr->left);
printTree(ptr->right);
}
else
std::cout << "NULL" << std::endl;

//std::cout << std::endl;
}

void updateSiblings(std::vector<tree_pointer> &vecPtr)
{
if(vecPtr.empty())
return;

std::vector<tree_pointer> vecPtrChild;
for(std::vector<tree_pointer>::iterator iter = vecPtr.begin(); iter != vecPtr.end(); iter++)
{
if((*iter)->left)
vecPtrChild.push_back((*iter)->left);
if((*iter)->right)
vecPtrChild.push_back((*iter)->right);
}

for(std::vector<tree_pointer>::iterator iter = vecPtrChild.begin(); iter != vecPtrChild.end(); iter++)
{
std::cout << (*iter)->data << " ";
if((iter+1) != vecPtrChild.end())
(*iter)->sibling = (*(iter+1));
}

std::cout << std::endl;

vecPtr.swap(vecPtrChild);
vecPtrChild.clear();

updateSiblings(vecPtr);
}

static HashMap<Integer, BTNode> levelMap = new HashMap<Integer, BTNode>();
	public static void updateSiblings(BTNode root, Integer level)
	{
		if(root==null)
			return;
		if(levelMap.containsKey(level))
		{
			levelMap.get(level).sibling = root;
		}
		levelMap.put(level, root);
		updateSiblings(root.left, new Integer(level.intValue()+1));
		updateSiblings(root.right, new Integer(level.intValue()+1));
	}
	
	public static void updateSiblings(BTNode root)
	{
		levelMap.clear();
		updateSiblings(root, new Integer(1));
	}

any traversal(pre/post/in-order) with proper null checks and sibling field updation instead of processing the root node will do this.

The given code will connect all the nodes which are at the same level. Simple BFS with storing each level.

typedef struct tree
{
tree *right;
tree *left;
tree *sibling;
int data;
}node;

void ConnectNodesAtSameLevel(node *start)
{
     queue<node*> Siblings;
     Siblings.push(start);
     node *current;
     node *previous = NULL;
     Siblings.push(NULL);
     while(Siblings.size() > 0)
     {
          current = Siblings.front();
          Siblings.pop();
          if(current == NULL)
          {
             if(Siblings.front() != NULL)
                Siblings.push(NULL);
             previous = NULL;
             continue;      
          }
          if(previous != NULL)
             previous->sibling = current;
          previous = current;
          if(current->left)Siblings.push(current->left);
          if(current->right)Siblings.push(current->right);
     }
     cout << start->left->left->sibling->sibling->data << endl;
}

void sibling(node *start)
{
if(start==NULL)
return;
if((start->left==NULL) && (start->right==NULL))
return;
else if(start->left && !start->right)
{
start->left->sibling=NULL;
sibling(start->left);
}
else if(start->right && !start->left)
{
start->right->sibling=NULL;
sibling(start->right);
}
else
{
start->left->sibling=start->right;
start->right->sibling=start->left;
sibling(start->left);
sibling(start->right);
}
return;
}

@gnu i think your idea is good

Printing nodes at same level would be printing out sibling right?? Can we do a level order traversal and print out nodes at that level?

public void FindSiblings(TreeNode root)
        {
            Queue<TreeNode> q = new Queue<TreeNode>();
            Queue<int> lq = new Queue<int>();
            q.Enqueue(root);
            lq.Enqueue(0);
            TreeNode previous = null;
            TreeNode current = null;
            int level = -1;
            int previousLevel = -1;
            while (q.Count > 0)
            {
                current = q.Dequeue();
                level = lq.Dequeue();
                if (current.Left != null)
                {
                    q.Enqueue(current.Left);
                    lq.Enqueue(level + 1);
                }
                if (current.Right != null)
                {
                    q.Enqueue(current.Right);
                    lq.Enqueue(level + 1);
                }
                if (previous != null && previousLevel == level)
                {
                    previous.Sibling = current;
                    Console.WriteLine(previous.Data + " : " + previous.Sibling.Data);
                }
                previous = current;
                previousLevel = level;
            }
        }

//Using DFS traversal
void addSibling(Node node)
if(node == null) return
if(node.left !=null)
node.left.sibling=node.right
if(node.right!=null
node.right.sibling=node.left
addSibling(node.left)
addSibling(node.right)

//Using BFS traversal
void addSibling(Node node)
Queue<Node> queue = new Queue<Node>()
queue.enqueue(node)
while((node=queue.dequeue())!=null)
if(node.left!=null)
node.left.sibling=node.right
queue.enqueue(node.left)
if(node.right!=null)
node.right.sibling=node.left
queue.enqueue(node.right)

//class TreeNode
        //{
        //    int data;
        //    TreeNode left = null;
        //    TreeNode right = null;
        //    TreeNode sibling = null;
        //    int level = -1;
        //}

        public void FixSiblingsPtr()
        {
            if (root == null) return;

            Queue tempQ = new Queue();

            root.Level = 0;
            tempQ.Enqueue(root);

            TreeNode prev = null;

            while (tempQ.Count > 0)
            {
                TreeNode node = tempQ.Dequeue() as TreeNode;

                if ((prev != null) && (node.Level == prev.Level))
                    prev.Sibling = node;

                prev = node;

                if (node.Left != null)
                {
                    node.Left.Level = node.Level + 1;
                    tempQ.Enqueue(node.Left);
                }
                if (node.Right != null)
                {
                    node.Right.Level = node.Level + 1;
                    tempQ.Enqueue(node.Right);
                }
            }
        }

Here is an implementation to connect the nodes at same level in O(1) space complexity

/*-----connect nodes at same level-------*/
void connect_nodes_at_same_level_Utility(struct node* root)
{

int num;
num= height(root);
struct node* prev= NULL;
int i;
if(root == NULL)
return;
//printf("%d\n",root->data);//print root data before moving further to any level
if(root->left == NULL && root->right== NULL)
return;
root->next= NULL;
for(i=1; i<num; i++)
{
connect_nodes_at_same_level(root,0,i,&prev);//keep printing elements at a particular level from the root
prev= NULL;

}


}


void connect_nodes_at_same_level(struct node* root, int n , int k, struct node** prev)
{

if(root != NULL)
{

connect_nodes_at_same_level(root->right,n+1,k,prev);
if( n== k)
{
root->next= *prev;
*prev= root;
}
connect_nodes_at_same_level(root->left,n+1,k,prev);

}

else
return 0;


}

Here is the recursive approach which takes O(1) space & O(N) time complexity.

connectNodesatSameLevel(root)// call it after making root->nextRight=NULL
{
	if(root)
	{
		if(root->nextRight)
			connectNodesatSameLevel(root->nextRight);
	
		if(root->left)
		{
			if(root->right)
			{
				root->left->nextRight=root->right;
				root->right->nextRight=findNextRight(root);
			}
			else
				root->left->nextRight=findNextRight(root);
			connectNodesatSameLevel(root->left);
		}
		else if(root->right)
		{
			root->right->nextRight=findNextRight(root);
			connectNodesatSameLevel(root->right);
		}
		else
			connectNodesatSameLevel(findNextRight(root));
	}	
}

findNextRight(root)
{
	root=root->nextRight;
	while(root)
	{
		if(root->left)
			return root->left;
		if(root->right)
			return root->right;
		root=root->nextRight;
	}
	return NULL;
}

Here is the iterative approach.
Space : O(1)
Time: O(N)

connectNodesatSameLevel(root)
{
	if(!root)
		return;
	root->nextRight=NULL;

	while(root)
	{
		p=root;
		while(p)
		{
			if(p->left)
			{
				if(p->right)
					p->left->nextRight=p->right;
				else
					p->left->nextRight=findNextRight(p);
			}
			if(p->right)
				p->right->nextRight=findNextRight(p);

			p=p->nextRight;
		}
		if(root->left)
			root=root->left;
		else if(root->right)
			root=root->right;
		else
			root=findNextRight(root);				
	}
	
}

findNextRight(root)
{
	root=root->nextRight;
	while(root)
	{
		if(root->left)
			return root->left;
		if(root->right)
			return root->right;
		root=root->nextRight;
	}
	return NULL;
}

void populateSibling(node *root)
{
   static node *p=NULL;
   if(root)
    { 
      root->sibling=p;
      p=root->right;
      populateSibling(root->left);
      populateSibling(root->right);
      p=root;
    }
   else
    p=NULL;
}

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

#include<conio.h>
#include<stdlib.h>
struct graph
{
	int value;
	struct graph *left;
	struct graph *right;
	struct graph *next;
}*root;
struct graph *creategraph(int k)
{
	struct graph *temp=malloc(sizeof(struct graph));
	temp->value=k;
	temp->left=NULL;
	temp->right=NULL;
	temp->next=NULL;
	return temp;
}
void connectLevel(struct graph *g)
{
	if(g==NULL)
	   return;
    if(g->left)
	{
		if(g->right)
		   g->left->next=g->right;
		else
		{
			struct graph *s=g->next;
			while(s)
			{
				if(s->left)
				{
			      g->left->next=s->left;
				  break;
			    }
			    if(s->right)
			    {
			    	g->left->next=s->right;
			    	break;
			    }
			    s=s->next;
			}
		}
	}
	if(g->right)
	{
			struct graph *s=g->next;
			while(s)
			{
				if(s->left)
				{
			      g->right->next=s->left;
				  break;
			    }
			    if(s->right)
			    {
			    	g->right->next=s->right;
			    	break;
			    }
			    s=s->next;
			}
	}
	connectLevel(g->left);
	connectLevel(g->right);

}
int main()
{
	root=creategraph(3);
	root->left=creategraph(2);
	root->left->right=creategraph(7);
	root->right=creategraph(4);
	root->right->right=creategraph(5);
	
	connectLevel(root);
	printf("%d",root->left->right->next->value);

}

public Node toSiblingTree(){
		this.root.next = null;
		return toSiblingTree(root);
	}
	
	public Node toSiblingTree(Node root){
		if(root == null) return null;
		Node left = root.left;
		Node right = root.right;
		if(right != null){
			if(left!=null)
			left.next = right;
			if(root.next == null){
				right.next = null;
			}
			else{
				right.next = root.next.left != null ? root.next.left : root.next.right ; 
			}
		}
		else if (left!=null){
			if(root.next == null)
					left.next = null;
			else{
				left.next = root.next.left != null ? root.next.left : root.next.right ;
			}
		}
		
		root.left = toSiblingTree(left);
		root.right = toSiblingTree(right);
		return root;
	}
	 
	public void printLevelOrder(Node root){
		if(root == null) return;
		Node temp =root;
		while(temp!=null){
			System.out.print(temp.num+" ");
			temp = temp.next;
		}
		System.out.println("");
		temp = root;
		Node left = temp.left != null ? temp.left : temp.right;
		while(left == null){
			if(temp == null || temp.next == null) break;
			temp = temp.next;
			left = temp.left != null ? temp.left : temp.right;
		}
		printLevelOrder(left);
		return;
	}

helps in printing level order

From leetcode.com/2010/03/first-on-site-technical-interview.html

Here is a more elegant solution. The trick is to re-use the populated nextRight pointers. As mentioned earlier, we just need one more step for it to work. Before we passed the leftChild and rightChild to the recursion function itself, we connect the rightChild’s nextRight to the current node’s nextRight’s leftChild. In order for this to work, the current node’s nextRight pointer must be populated, which is true in this case. Why? Try to draw a series of diagram how the recursion deepens, you will immediately see that it is doing DFS (Depth first search).

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);
}

here is the complete working code here in C

#include<stdio.h>
#include<stdlib.h>
struct Tree
{
int key;
struct Tree* left;
struct Tree *right;
struct Tree *nextright;
}*root=NULL;
void displaytree(struct Tree *);
void conASL(struct Tree *);
int main()
{
struct Tree *temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
root =temp;
root->key=2;
root->nextright=NULL;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=3;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->left=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=4;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->right=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=5;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->left->left=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=6;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->left->right=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=7;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->right->left=temp;
temp= (struct Tree*)malloc(sizeof(struct Tree));
temp->key=8;
temp->left=NULL;
temp->right=NULL;
temp->nextright=NULL;
root->right->right=temp;
conASL(root);
displaytree(root);
return 0;
}
void displaytree(struct Tree *node)
{
    if(node==NULL)
        return;
printf("key=%d",node->key);
if(node->nextright==NULL)
printf("nextright=NULL");
else
printf("nextright=%d",node->nextright->key);
displaytree(node->left);
displaytree(node->right);
}
void conASL(struct Tree *node)
{
    if((node->left==NULL)&&(node->right==NULL))
        return;
    else
    {
        node->left->nextright=node->right;
        if(node->nextright==NULL)
        {
            node->right->nextright=NULL;
        }
        else
        {
        node->right->nextright=node->nextright->left;
        }
   conASL(node->left);
   conASL(node->right);
    }

}