## Arista Networks Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

Do an in-order traversal of the tree and if its in sorted order then it means its a BST. correct me if I am wrong.

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

public static bool ValidateBST(Tree root,int MaxValue, int MinValue)
{

if (root != null)
{
if (root.Data > MinValue && root.Data < MaxValue && ValidateBST(root.left, root.Data, int.MinValue) && ValidateBST(root.right, int.MaxValue, root.data))
return true;
else
return false;
}

return true;

}

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

this algorithm is not efficient as finding MinValue and MaxValue is not trivial. It involves traversing the entire left/right tree.

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

in order to validate if a tree is BST we will have to make sure all nodes are traversed. How can we say for sure a tree is BST w/o traversing all nodes ?
Plus calculating min and max values is done by function itself.....the call from main can pass -infinity as min value and +infinity as max value (or int.min and int.max)

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

The above solution is wrong
Check out this..
6
2 9
1 7 3 11
The above tree will satisfy all your check but is not a BST.
Inorder will shorted array..

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

6
2 9
1 7 3 11

This tree cannot be a BST. For a tree to be a BST, every node to the left of root should be smaller than the root and every node to the right of root should be greater than the root. In this case, 7 cannot be on the left of 6. And 3 cannot be on the right.

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

This will work perfectly. In-Order traversal is another solution.

However with your solution what's the space complexity? O(height)?

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

this approach uses recursion as shown above

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

I think the previous code is too complicated, below code is simpler by using in order

``````Bool checkbst(node * node,  int & previous value)
{
If (node == null)
Return true;

Bool result  = checkbst(node.left,   Previous);
If (!result). Return false;
If( previous > node.value)
Return false;
Return checkbst( node.right,  node.value)

}``````

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

Sorry forget to do
Previoxus = node.value
Then return checkbst(node.left, previous)

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

Check if the entire tree satisfies the following condition:

left(current_node).value < current_node.value &&
right(current_node).value >= current_node.value

where left(current_node) returns the pointer to left child of the current node and
right(current_node) returns the pointer to right child of the current node.

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

typedef struct node {
int data;
struct node* left;
struct node* right;
} Node;

/* return 1 if true - 0 if false - even if one node return false*/
return 0;
}
return 1;
}

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.