Arista Networks Interview Question Software Engineer / Developers
0of 0 votesCheck if a tree is a BST.
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