## Arista Networks Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**In-Person

I have provided the successor method as a part of class Tree below.

class node{

public:

int key;

node* left;

node* right;

node(int key) {

this->key = key;

left = right = 0;

}

};

class Tree{

node* root;

public:

Tree(node *p):root(p) {}

void addNode(int key) {

node *p = new node(key);

addNode(p);

}

node* find(int key) {

node* curr = root;

while(curr) {

if (curr->key == key) {

return curr;

}

if (curr->key < key) {

curr = curr->right;

} else {

curr = curr->left;

}

}

return NULL;

}

node* succussor(int key) {

node *p = find(key);

if(!p) {

cout<<"Cannot find "<<key<<endl;

return NULL;

}

if (p->right) { //Go one right and then left all the way till end

p = p->right;

for(;p->left;p=p->left);

return p;

} else { //successor the "nearest" ancestor to node p such that p is in the left

//subtree of the successor

node *curr = root,*successor = 0;

while(curr) {

if (curr->key == p->key) {

if (!successor) cout<<key<<" doesn't have any successor!"<<endl;

return successor;

}

if (curr->key < p->key) {

curr = curr->right;

} else {

successor = curr;

curr = curr->left;

}

}

}

}

};

Solution: Exploit Binary Search Algorithm such that when key is found on node N,

a) if N has a right sub tree -- the leftmost node is the successor

b) if N does not has --> simply mark isFound (optional, not needed when we are guarantee the key is always found in the tree)

c) for the earliest ancestor of N where the left sub tree contains key (isFound but succ is null) --> it is the successor.

```
global isFound = false;
Node getSuccessor(Node root, int key){
//base case
if(root.val == key ){
isFound = true;
if(root.right != null)
return getLeftMost(root.right);
else
return null;
}
//recursive
Node succ;
if(root.val > key){
succ = getSuccessor(root.left, key);
if(isFound && succ == null) succ = root;
}else{
succ = getSuccessor(root.right, key);
}
return succ;
}
```

Using recursion it can be done as follows:

- Dee January 15, 2012public static Tree InorderSuccessor(int value, Tree root, ref Tree caller, ref Tree successor)

{

if (root != null)

{

InorderSuccessor(value,root.Left, ref root, ref successor);

if (root.Data == value)

successor = caller;

InorderSuccessor(value, root.Right, ref root, ref successor);

}

return successor;

}

So the idea is to traverse the tree in in-order format. The caller of the function will always be the successor.

When you call from main the call will look like this

Tree succ = null;

int value; assing this to the value of node for which you need the successor for.

succ = InorderSuccessor(value,root, ref succ, ref succ);