CareerCup

struct Node
{
  int data;
  Node* right;
  Node* left;
  Node* RightNeighbor;
}

void UptateTreeToPointToRightNeighbor(Node* head)
{
  if(!head)
    return null;
    
  Queue<Node*> myQ = new Queue();
  myQ.push(head);
  myQ.push(NULL);  
  
  while(!myQ,IsEmpty)
  {
    Node* curr = myQ.Dequeue();
    
    if(curr)
    {
      curr->RightNeighbor = myQ.Front;
      if(curr->left)
        myQ.push(curr->left);
      if(curr->right)
        myQ.push(curr->right);
    }
    else
        myQ.push(NULL);
  }
}

Do level order traversal, and then assign neighbor accordingly as done by JSDUDE

struct btree {
	int data;
	struct btree* left;
	struct btree* right;
	struct btree* neighbor;
};

Recursive:

void set_neighbor(struct btree* bt) {
	if(!bt || !bt->right)
		return;
	if(bt->right && bt->left)
		bt->left->neighbor = bt->right;
	set_neighbor(bt->left);
	set_neighbor(bt->right);
}

Iterative:

void set_neighbor(struct btree* bt) {
	if(!bt || !bt->right)
		return;
	stack<struct btree*> sbt;
	if(bt) sbt.push(bt);
	while(!sbt.empty()) {
		struct btree* tmp = sbt.peek();
		if(tmp->left && tmp->right)
			tmp->left->neighbor = tmp->right;
		sbt.pop();
		if(tmp->left) sbt.push(tmp->left);
		if(tmp->right) sbt.push(tmp->right);
	}
	return;
}

/* This function returns the leftmost child of nodes at the same level as p.
   This function is used to getNExt right of p's right child
   If right child of is NULL then this can also be sued for the left child */
struct node *getNextRight(struct node *p)
{
    struct node *temp = p->nextRight;

    /* Traverse nodes at p's level and find and return
       the first node's first child */
    while (temp != NULL)
    {
        if (temp->left != NULL)
            return temp->left;
        if (temp->right != NULL)
            return temp->right;
        temp = temp->nextRight;
    }

    // If all the nodes at p's level are leaf nodes then return NULL
    return NULL;
}

/* Sets nextRight of all nodes of a tree with root as p */
void connect(struct node* p)
{
    struct node *temp;

    if (!p)
      return;

    // Set nextRight for root
    p->nextRight = NULL;

    // set nextRight of all levels one by one
    while (p != NULL)
    {
        struct node *q = p;

        /* Connect all childrem nodes of p and children nodes of all other nodes
          at same level as p */
        while (q != NULL)
        {
            // Set the nextRight pointer for p's left child
            if (q->left)
            {
                // If q has right child, then right child is nextRight of
                // p and we also need to set nextRight of right child
                if (q->right)
                    q->left->nextRight = q->right;
                else
                    q->left->nextRight = getNextRight(q);
            }

            if (q->right)
                q->right->nextRight = getNextRight(q);

            // Set nextRight for other nodes in pre order fashion
            q = q->nextRight;
        }

        // start from the first node of next level
        if (p->left)
           p = p->left;
        else if (p->right)
           p = p->right;
        else
           p = getNextRight(p);
    }
}

#include <stdio.h>
#include "iostream"
#include <conio.h>

using namespace std;

struct node
{
	int data;
	node* leftChild;
	node* rightChild;
	node* rightNeighbour;
};
class SetRightChild
	{
    public:node* root;	
	public:SetRightChild()
		   {
			   root = new node();
		   }
	public:node* SetTree()
	{
		
		root->data = 2;
		node* leftNode = new node();
		node* rightNode = new node();

		leftNode->data = 1;
		leftNode->leftChild = NULL;
		leftNode->rightChild = NULL;
		leftNode->rightNeighbour = NULL;
		root->leftChild = leftNode;

		rightNode->data = 3;
		rightNode->leftChild = NULL;
		rightNode->rightChild = NULL;
		rightNode->rightNeighbour = NULL;
		root->rightChild = rightNode;
		return root;
	}

	public:void SetRightNeighbour(node* rootNode)
	{
		if(rootNode == NULL)
		{
			return;
		}		
		if(rootNode->leftChild != NULL && rootNode->rightChild != NULL)
		{
			rootNode->leftChild->rightNeighbour = rootNode->rightChild;
		}
		SetRightNeighbour(rootNode->leftChild);
		SetRightNeighbour(rootNode->rightChild);
	}

	public:void printTree(node* rootNode)
	{
		if(rootNode != NULL)
		{
			cout<<"Node: "<<rootNode->data<<endl;
			if(rootNode->leftChild != NULL)
			{
				cout<<"LeftChild: "<<rootNode->leftChild->data<<endl;
			}
			if(rootNode->rightChild != NULL)
			{
				cout<<"RightChild: "<<rootNode->rightChild->data<<endl;
			}
			if(rootNode->rightNeighbour != NULL)
			{
				cout<<"RightNeighbour: "<<rootNode->rightNeighbour->data<<endl;
			}			
		
		
		if(rootNode->leftChild != NULL)
		{
			printTree(rootNode->leftChild);
		}
		if(rootNode->rightChild != NULL)
		{
			printTree(rootNode->rightChild);
		}
		}
	}

		
	
};
	void main()
	{	
		SetRightChild* tree = new SetRightChild();
		tree->root = tree->SetTree();
		cout<<"before setting rightneighbour: "<<endl;
		tree->printTree(tree->root);
		
		tree->SetRightNeighbour(tree->root);

		cout<<"after setting rightneighbour: "<<endl;
		tree->printTree(tree->root);

		_getch();		
	}

Iterative approach. Time complexity: O(n) and O(1) space complexity.
Here we use the populated sibling ptr to traverse the tree in the zigzag manner and populate the sibling ptr of root's child.

Code:

public BinaryTreeNode populateSiblingPtr(BinaryTreeNode root) {
		if (root == null)
			return null;
		BinaryTreeNode finalRoot = root;
		root.sibling = null;
                //start will have first node at from left at next level
		BinaryTreeNode start = root.left != null ? root.left : root.right;
		while (root != null) {
			if (root.left != null)
				root.left.sibling = root.right;
			if (root.right != null)
				root.right.sibling = root.sibling == null ? null : root.sibling.left;
			if (start == null)
				start = root.left != null ? root.left : root.right;
			if (root.sibling == null) {
				root = start;
				if (start != null)
					start = start.left != null ? start.left : start.right;
			} else
				root = root.sibling;

		}
		return finalRoot;
	}

public static void SetNeighbour(Node1 n)
        {
            if (n == null)
                return;

            if (n.left != null)
                n.left.neighbour = n.right;

            if (n.right != null && n.neighbour != null)
                n.right.neighbour = n.neighbour.left;

            SetNeighbour(n.left);
            SetNeighbour(n.right);

            return;
        }

public static void SetNeighbour(Node1 n)
        {
            if (n == null)
                return;

            Queue<Node1> q = new Queue<Node1>();
            q.Enqueue(n);
            
            while (q.Count > 0)
            {
                Node1 current = q.Dequeue();
                if (current.left != null)
                    current.left.neighbour = current.right;

                if (current.right != null && current.neighbour != null)
                    current.right.neighbour = current.neighbour.left;

                if(current.left != null)
                    q.Enqueue(current.left);

                if (current.right != null)
                    q.Enqueue(current.right);
            }

            return;
        }

Public void ConnectSibling(node root, int depth, List<node> prev)
{
if(root==null)
return;
if(prev.count<=depth)
Prev.Add(root);
else
{
Prev[depth].sibling=root;
Prev[depth]=root;
}
Connect(root.left,depth+1,prev);
Connect(root.right,depth+1,prev);
}

class Node
	{
	public:
		int data;
		Node* right;
		Node* left;
		Node* nebihor;
		Node():right(NULL),left(NULL),nebihor(NULL){}
	};
	void getLevels(Node* node,int level, vector<vector<Node*>>&levels)
	{
		if(node==NULL)
			return;
		if(levels.size()<level+1)
		{
			vector<Node*> nodes;
			levels.push_back(nodes);
		}
		levels[level].push_back(node);
		getLevels(node->left,level+1,levels);
		getLevels(node->right,level+1,levels);
	}
	void makeNeighbours(Node* node)
	{
		vector<vector<Node*>> levels;
		getLevels(node,0,levels);
		for(int i=0; i< levels.size();i++)
			for(int j=0;j<levels[i].size()-1;j++)
				levels[i][j]->nebihor=levels[i][j+1];
	}

An iterative solution: level by level with constant space (no stack/queue).
An recursive solution: using a HashMap to record the current first node of each level, each time we deal with the current root node first and then its right child and then its left child.
Another recursive solution: adapted from the iterative solution.

public class ID17808664
{
	private HashMap<Integer, TreeNode> m_level2firstNode=new HashMap<Integer, TreeNode>();
	public void linkSiblingRecursion(TreeNode root)
	{// recursion with recording the current first node for each level in HashMap
		linkSiblingRecursion(root, 0);
	}
	private void linkSiblingRecursion(TreeNode root, int level)
	{// root, right, left
		if (root==null)
			return;
		// the current first node on the same level as root
		TreeNode currentFirstNode=m_level2firstNode.get(level);
		root.next=currentFirstNode;
		m_level2firstNode.put(level, root);// update
		// next level
		linkSiblingRecursion(root.right, level+1);
		linkSiblingRecursion(root.left, level+1);
	}
	public void linkSiblingRecursion2(TreeNode root)
	{// essentially it is still iteration
		if (root==null)
			return;
		TreeNode firstOfNextLevel=root;
		// one level down
		TreeNode parent=firstOfNextLevel;
		firstOfNextLevel=null;
		TreeNode previous=null;
		TreeNode node=null;
		while (parent!=null)
		{
			if (parent.left!=null)
			{
				node=parent.left;
				if (previous!=null)
						previous.next=node;
				else
					firstOfNextLevel=node;
				previous=node;
			}
			if (parent.right!=null)
			{
				node=parent.right;
				if (previous!=null)
					previous.next=node;
				else
					firstOfNextLevel=node;
					previous=node;
			}
			parent=parent.next;
		}
		linkSiblingRecursion2(firstOfNextLevel);
	}
	
	public void linkSiblingIteration(TreeNode root)
	{// level by level
		TreeNode firstOfNextLevel=root;
		while (firstOfNextLevel!=null)
		{
			// one level down
			TreeNode parent=firstOfNextLevel;
			firstOfNextLevel=null;
			TreeNode previous=null;
			TreeNode node=null;
			while (parent!=null)
			{
				if (parent.left!=null)
				{
					node=parent.left;
					if (previous!=null)
						previous.next=node;
					else
						firstOfNextLevel=node;
					previous=node;
				}
				if (parent.right!=null)
				{
					node=parent.right;
					if (previous!=null)
						previous.next=node;
					else
						firstOfNextLevel=node;
					previous=node;
				}
				parent=parent.next;
			}
		}
	}
	
	public static void main(String[] args)
	{
		ID17808664 wpd=new ID17808664();
		TreeNode root=wpd.new TreeNode(1);
		root.left=wpd.new TreeNode(2);
		root.right=wpd.new TreeNode(3);
		root.left.left=wpd.new TreeNode(4);
		root.left.right=wpd.new TreeNode(5);
		root.right.left=wpd.new TreeNode(6);
		root.right.right=wpd.new TreeNode(7);		
		root.left.left.left=wpd.new TreeNode(8);
		root.left.left.right=wpd.new TreeNode(9);
		root.right.left.left=wpd.new TreeNode(10);
		root.right.left.right=wpd.new TreeNode(11);
		root.right.right.right=wpd.new TreeNode(12);
		
		System.out.println(root.toStringAll());
		wpd.linkSiblingIteration(root);
		System.out.println(root.toStringAll());
		
		root=wpd.new TreeNode(1);
		root.left=wpd.new TreeNode(2);
		root.right=wpd.new TreeNode(3);
		root.left.left=wpd.new TreeNode(4);
		root.left.right=wpd.new TreeNode(5);
		root.right.left=wpd.new TreeNode(6);
		root.right.right=wpd.new TreeNode(7);		
		root.left.left.left=wpd.new TreeNode(8);
		root.left.left.right=wpd.new TreeNode(9);
		root.right.left.left=wpd.new TreeNode(10);
		root.right.left.right=wpd.new TreeNode(11);
		root.right.right.right=wpd.new TreeNode(12);
		wpd.linkSiblingRecursion(root);
		System.out.println(root.toStringAll());
		
		root=wpd.new TreeNode(1);
		root.left=wpd.new TreeNode(2);
		root.right=wpd.new TreeNode(3);
		root.left.left=wpd.new TreeNode(4);
		root.left.right=wpd.new TreeNode(5);
		root.right.left=wpd.new TreeNode(6);
		root.right.right=wpd.new TreeNode(7);		
		root.left.left.left=wpd.new TreeNode(8);
		root.left.left.right=wpd.new TreeNode(9);
		root.right.left.left=wpd.new TreeNode(10);
		root.right.left.right=wpd.new TreeNode(11);
		root.right.right.right=wpd.new TreeNode(12);
		wpd.linkSiblingRecursion2(root);
		System.out.println(root.toStringAll());

	}
	public class TreeNode
	{
		public TreeNode left=null;
		public TreeNode right=null;
		public TreeNode next=null;
		int val;
		public TreeNode(int v)
		{
			val=v;
		}
		public String toString()
		{
			return String.format("[TreeNode: val=%d]", val);
		}
		public String toStringAll()
		{
			return String.format("[TreeNode: val=%d, left=%s, right=%s, next=%s]", val, 
					(left!=null) ? left.toStringAll() : null, 
					(right!=null) ? right.toStringAll() : null,
					next);
		}
	}
}