Answer
Binary search tree (BST) is a binary tree which has the following properties:
1. Tree is a binary tree
2. The left subtree of a node contains only nodes with keys less than the node's key.
3. The right subtree of a node contains only nodes with keys greater than the node's key.
Based on the definition above, the simpliest solution to verify if binary tree is a search binary tree (BST) would be to in-order travers the tree and validate that the output is sorted. An inorder traversal means printing the left node first, then printing the parent node, and printing the right node last.
Sample answer:
The optimization would in incorporate check into traversal
Company where asked this question: Amazon
Interviewed for position: SDE, SDET
Binary search tree (BST) is a binary tree which has the following properties:
1. Tree is a binary tree
2. The left subtree of a node contains only nodes with keys less than the node's key.
3. The right subtree of a node contains only nodes with keys greater than the node's key.
Based on the definition above, the simpliest solution to verify if binary tree is a search binary tree (BST) would be to in-order travers the tree and validate that the output is sorted. An inorder traversal means printing the left node first, then printing the parent node, and printing the right node last.
Sample answer:
List<int> unfolded = new List<int>();
public void travers(TreeNode node)
{
if (node != null)
{
unfolded.Add(validate(node.left));
unfolded.Add(node.value.ToString());
unfolded.Add(validate(node.right));
}
}
public bool validate(TreeNode node)
{
unfolded = new List<int>();
travers(node);
var array = unfolded.toArray();
for(int i=1;i<array.lenght; i++)
{
if (array[i-1] > array[i]) return false;
}
return true;
}
The optimization would in incorporate check into traversal
Company where asked this question: Amazon
Interviewed for position: SDE, SDET
