Arista Networks Interview Question
Software Engineer / DevelopersCountry: 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);