CareerCup

1) Store the tree in an array by using modified BreadthFirstSearch(but dont remove any node from the array).
So the tree {1
2 3
4 5 6}
will be stored as 1 * 2 3* 4 5 6*.
2) Now in the array if the element is not '*' make its rightnode as the next element in the array, if the next element is '*' assign 'NULL.

Woud this work?

void connectRight(Node *t, Node *nextRight) {
if (!t)
return;
t->nextRight = nextRight;
connectRight(t->leftChild, t->rightChild);
if (nextRight)
connectRight(t->rightChild, nextRight->leftChild);
else
connectRight(t->rightChild, NULL);
}

void connect(Node *t) {
connectRight(t, NULL);
}

can you clarify please? Populate it with what?

void PopulateNext(Node** root)
{
Node* tempNode = *root;

if (tempNode == NULL)
{
return;
}


if (tempNode->left)
{
tempNode->left->next = tempNode->right;
}

if (tempNode->right)
{
tempNode->right->next = temp->next->left;
}

PopulateNext(&tempNode->left);
PopulateNext(&tempNode->right);
}

Will this work?

Can you provide some example?

the question is to implement morris algorithm??

/*A binary tree is given with left and right populated but the nextRight pointers in each node are not populated. Populate the nextRight pointer in each node.*/

package BST;

public class PopulateNextRight {

	BST bst = new BST();
	public PopulateNextRight() {
		bst.createDummyBST();
		bst.printBSTInOrder(bst);
		populate(bst);
		printLastRights(bst);
	}
	private void printLastRights(BST node) {
		if(node == null)
			return;
		BST dummyNode = node;
		while(dummyNode != null) {
			System.out.print(dummyNode.data + " ");
			dummyNode = dummyNode.nextRight;
		}
		System.out.println();
		printLastRights(node.left);
		printLastRights(node.right);
	}
	public void populate(BST node){
		if(node == null) {
			return;
		}
		if(node.right !=null && node.left !=null) {
			node.left.nextRight = node.right;
			assignNextRight(node.right,node.nextRight);
		}
		else if(node.right !=null) {
			assignNextRight(node.right,node.nextRight);
		}
		else if(node.left !=null){
			assignNextRight(node.left,node.nextRight);
		}
		populate(node.left);
		populate(node.right);
	}
	void assignNextRight(BST node, BST uncle){
		if(uncle == null)
			return;
		if(uncle.left !=null)
			node.nextRight = uncle.left;
		else if(uncle.right !=null)
			node.nextRight = uncle.right;
		else 
			assignNextRight(node, uncle.nextRight);
	}
	
}

/*just putting in a bit of logic: root(left, right/*ignore everything on the left, and start on the right side*/)*/
public class Node {
Node left;//left node
Node right;//right node;
int Value;
public Node(int a){
Value = a;
left = null;
right = null;
}
public void add(int a){
if(a > Value){
if(right == null)
right = new Node(a);
else
right.add(a);//recursive call
}else{
/*this would mean that the node is smaller than the root value
* and would thus be added to the left.But that's not part of the question
*/
}
}
}

A simple inorder traverse:

static void populateNextRight(BinaryNode node, BinaryNode parent)
{
     if(node != null)
     {
          populateNextRight(node.left, node);
          if(parent != null && node != parent.right)
          {
               node.nextRight = parent.right;
	  }	 
          populateNextRight(node.right, node);
      }
}
static class BinaryNode
{
     int data;
     BinaryNode left;
     BinaryNode right;
     BinaryNode nextRight;
 
     BinaryNode(int data)
     {
          this.data = data;
     }
}

Here is mine :

Class Node {
	int value;
	Node nextRight;
	Node left;
	Node right;
}

void fillNextRight (Node root) {
	if (root == null) 
		return;
	
	Node current = root;
	Node nextLevelStart = root;
while (nextLevelStart != null) {
	current = nextLevelStart;
	nextLevelStart = null;
	Node nextLevelLast = null;
while (current != null) {
fillValues( nextLevelStart, nextLevelLast, current.left);
fillValues( nextLevelStart, nextLevelLast, current.right);
current=current.nextRight;	
}
}
}

void fillValues (Node nextLevelStart,Node nextLevelLast, Node nextLevelCurrent) {
	if (nextLevelCurrent != null) {
		if (nextLevelStart == null) nextLevelStart == nextLevelCurrent;
		if (nextLevelLast != null) {
			nextLevelLast.rightNode = nextLevelCurrent;
}
nextLevelLast = nextLevelCurrent;
}
}

public class NextNode{

public static class Tree<T> {

T data;
Tree<T> left;
Tree<T> right;
Tree<T> rightNode;

public Tree(T data) {
this.data = data;
}
}

static int count = 0;
public static void populateRight(Tree<Integer> t, Tree<Integer>[] ar) {
if(t == null) return;
populateRight(t.left, ar);
ar[count] = t;
count++;
populateRight(t.right, ar);
ar[count] = null;
}

public static void populateRt(Tree<Integer> t, Tree<Integer>[] ar) {
for(int i = 0; ar[i] != null; i++){
ar[i].rightNode = ar[i+1];
}
}

public static void main(String[] args) {
Tree<Integer> t = new Tree<Integer>(1);
Tree<Integer> t1 = new Tree<Integer>(2);
Tree<Integer> t2 = new Tree<Integer>(3);
Tree<Integer> t3 = new Tree<Integer>(4);
Tree<Integer> t4 = new Tree<Integer>(5);
Tree<Integer> t5 = new Tree<Integer>(6);
Tree<Integer> t6 = new Tree<Integer>(7);
t.left = t1;
t.right = t2;
t1.left = t3;
t1.right = t4;
t2.left = t5;
t2.right = t6;
//populate tree;
Tree<Integer>[] ar = new Tree[10];
populateRight(t, ar);
populateRt(t, ar);
System.out.println(t);
}
}

struct Node
{
Node *Left;
Node *Right;
Node *NextRight;
};

typedef Node* PTR;

void F(PTR &Q1, PTR &Q2)
{
Node * C2 = NULL;

while(NULL != Q1)
{
if(NULL != Q1->Left)
{
if(NULL == Q2)
{
Q2 = Q1;
}
else
{
C2->NextRight = Q1->Left;
}

C2 = Q1->Left;
}

if(NULL != Q1->Right)
{
if(NULL == Q2)
{
Q2 = Q1;
}
else
{
C2->NextRight = Q1->Right;
}

C2 = Q1->Right;
}

Q1 = Q1->NextRight;
}
}

struct Node
{

Node *Left;

Node *Right;

Node *NextRight;
};

typedef Node* PTR;

void F(PTR &Q1, PTR &Q2)
{

Node * C2 = NULL;

while(NULL != Q1)

{

if(NULL != Q1->Left)

{

if(NULL == Q2)

{

Q2 = Q1;

}

else

{

C2->NextRight = Q1->Left;

}

C2 = Q1->Left;

}

if(NULL != Q1->Right)

{

if(NULL == Q2)

{

Q2 = Q1;

}

else

{

C2->NextRight = Q1->Right;

}

C2 = Q1->Right;

}

Q1 = Q1->NextRight;

}

}

void Sibling(Node *T)
{

if(NULL != T)

{

Node *Q1 = T;

Node *Q2 = NULL;

while(NULL != Q1 || NULL != Q2)

{

F(Q1, Q2);

F(Q2, Q1);

}

}
}

I did it by doing the inorder traversal of the node and keeping track of the last visited node. The last visited node connected to the next pointer. Not sure if this is correct.

Class Node {
Node left;
Node right;
Node nextRight;
}

void updateNextRight(Node root) {
  Node lastVisited = null;
 updateNextRightPointers( root, lastVisited );
}

void updateNextRightPointers( Node node, Node lastVisited) {
if( node == null ) return;
updateNextRightPointers(node.left,lastVisited);
if(lastVisited != null) {
  lastVisited.nextRight = root;
} 
lastVisited = root;
updateNextRightPointers( node.right, lastVisited);
}