CareerCup

Write functions:-
-> Node * Successor(Node * n)
-> Node * Predecessor(Node * n)

Suppose you have to insert a node having node pointer k.
Now k1 = Successor(k)
k2 = Predecessor(k)

and then do the following changes:-

k2->rand = k;
k->rand = k1;

These changes were made because before insertion of k, k2->rand was pointing to k1.

node* FindLeftMost(node *n)
{
while(n->left != NULL)
n = n->left;
return n;
}

node * inOrderSuccessor(node *n, node *pred)
{
// step 1 of the above algorithm
if( n->right != NULL )
return FindLeftMost(n->right);

// step 2 of the above algorithm
return pred;
}

void Recurse(tree *root, tree *pred)
{
if(root == NULL) return;
node *temp = inOrderSuccessor(root, pred);
if(root->rand != temp)
root->rand = NULL;
Recurse(root->left, root);
Recurse(root->right, pred);
}

int main(void)
{
Recurse(root, NULL);
}

I think this code will be sufficient for all the three cases. It does not matter if it is BST or binary.

void foo(Node root)
{
	Node prev = null;
	if(root == null)
	{
		return;
	}
	
	foo(root.left);
	
	if(prev != null && prev.random == root)
	{
		// okay !!!
	}
	else
	{
		prev.random = null
	}
	prev = root;

	foo(root.right);
}