## Arista Networks Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

Using recursion it can be done as follows:

public 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);

Comment hidden because of low score. Click to expand.
0
of 0 vote

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) {}
node *p = new node(key);
}

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.