CareerCup

Approach:
=========
We can implement it using BFS search ...
1. Use a queue and add root node inside it.
2. Now iterate over queue untill it not empty

Algorithm:
==========
Queue level1 = new Queue();
level1.add(rootNode);
Node lastNode = null;
while(!level1.isEmpty()){
	Node currentParent = queue.dequeue();
	Queue level2 = new Queue()
	if(currentParent.hasLeftNode()){
		Node leftChild = currentParent.leftNode();
		if(lastNode != null){
			lastNode.next() =  leftChild;
		}
		lastNode = leftChild;
		level2.add(leftChild);
	}
	if(currentParent.hasRightNode()){
		Node rightChild = currentParent.rightNode();
		if(lastNode != null){
			lastNode.next() =  rightChild;
		}
		lastNode = rightChild;
		level2.add(rightChild);
	}

}

Is the next pointer supposed to point to the node on the same level? If yes what happens if there are no nodes on the right at a give level.

I have attempted a possible solution, but may still needs to be refined/corrected

change_tree(struct node *root)
{

if (root == NULL)
   return;
root->next = NULL;
if (root->left) 
  root->left->next = root->right;
if (root->right)
  root->right->next = NULL;

if (root->left){
  assign_next_from_parent(root->left->left,root->left);
  assign_next_from_parent(root->left->right,root->left);
}
if (root->right) {
  assign_next_from_parent(root->right->left,root->left);
  assign_next_from_parent(root->right->right,root->left);
}

assign_next_from_parent(struct node *node, struct node *parent)
{
  if(parent->right)
    node->next = parent->right;
  elseif (parent->next) {
   if (parent->next->left)node->next = parent->next->left;
   else   node->next = parent->next->right;

  } else {
     node->next = NULL;
 }

assign_next_from_parent(node->left,node);
assign_next_from_parent(node->right, node);

}

I have a solution O(1) space and O(n) time, where n - number of nodes.

void connect(TreeLinkNode *root) {
        if(!root) return;
        TreeLinkNode * cur = root;
        root -> next = NULL;
        while( cur -> left ){
            
            TreeLinkNode * connect = cur;
            while (connect -> next){
                connect -> left -> next = connect -> right;
                connect -> right -> next = connect -> next -> left;
                connect = connect -> next;
            }
            cur = cur -> left;
            connect -> left -> next = connect -> right;
            connect -> right -> next = NULL;
            
        }

#include <iostream>
#include <string>
#include <queue>
using namespace std;

struct TreeNode {
	int data;
	TreeNode* left;
	TreeNode* right;
	TreeNode* thePtr;

	TreeNode(int data) : data(data), left(NULL), right(NULL) {}
	TreeNode(int data, TreeNode* left, TreeNode* right) : data(data), left(left), right(right) {}
};


void addLinks(TreeNode* root) {
	if (!root) return;
	queue<TreeNode*> nq;
	nq.push(root);
	nq.push(NULL);
	TreeNode* prev = NULL;

	while (!nq.empty()) {
		TreeNode *t = nq.front();
		nq.pop();
		if (prev)
			prev->thePtr = t;
		prev = t;
		if (t && t->left)
			nq.push(t->left);
		if (t && t->right)
			nq.push(t->right);
		if (!t && !nq.empty())
			nq.push(t);
	}
}

TreeNode* makeNode(int data, TreeNode *left = NULL, TreeNode *right = NULL) {
	return new TreeNode(data, left, right);
}


void printLinks(TreeNode *root) {
	TreeNode* t = root;
	while (t) {
		cout << t->data << ": ";
		TreeNode* tptr = t;
		while (tptr) {
			cout << tptr->data << " ";
			tptr = tptr->thePtr;
		}
		cout << endl;
		t = t->left;
	}
}

void test_addLinks() {
	TreeNode *root = makeNode(10);
	root->left = makeNode(12);
	root->right = makeNode(15);

	root->left->left = makeNode(8, makeNode(9), makeNode(4));
	root->left->right = makeNode(14, NULL, makeNode(7));

	root->right->left = makeNode(45, makeNode(2), makeNode(11));
	root->right->right = makeNode(26, NULL, makeNode(12));


	addLinks(root);
	printLinks(root);
}


int main() {
	test_addLinks();
	cin.ignore();
}

1) Find the height of the tree.
2) Use loop from 1 to height of tree for level traversal of the tree.
3) Add all nodes of the same level to a queue and link them.

1) Find the height of the tree.
2) Use loop from 1 to height of tree for level traversal of the tree.
3) Add all nodes of the same level to a queue and link them.

No assumption seems to be made about the the data structure of the binary tree. If its implemented as an array, then finding nodes to the right boils down to a matter of just examining the index.

#include <vector>

struct node
{
	unsigned data;
	bool is_null;
	node *right;
}

void connect_right(vector<node> tree)
{
	for(int i = 0; i < tree.size; i++)
	{
		if(!tree[i].is_null)
		{
			for(int j = i + 1; (j & (j + 1)) == 0; j++)
			{
				if(!tree[j].is_null)
				{
					tree[i].right = tree + j;
				}
			}
		}
	
	}
}