## Arista Networks Interview Question

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

**Interview Type:**In-Person

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;

}

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

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)

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..

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.

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

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.

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*/

int checkIfBST(Node *head) {

if (head!=NULL) {

if ((head->left && (head->left)->data > head->data) ||

(head->right && (head->right)->data < head->data) ||

!checkIfBST(head->right) ||

!checkIfBST(head->left))

return 0;

}

return 1;

}

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.

- Xyz January 14, 2012