## Citrix System Inc Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**In-Person

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

Write functions:-

- Neeraj September 13, 2011-> 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.