Amazon Interview Question: Write a method to decide if t... | Glassdoor

## Interview Question

Software Development Engineer In Test || Interview Seattle, WA

# Write a method to decide if the given binary tree is a

binary search tree or not.

3

for binary search tree, inorder traversal should result in sorted array in the increasing order.

Interview Candidate on Mar 14, 2012
0

Further, know that the difference between the two is that a binary search tree cannot contain duplicate entries.

recur down the tree
- check if element is already in hashtable
- - if it is, return false
- - if it isnt, insert element into the hashtable
- - - recur to children

Anon on Mar 16, 2012
4

I'm sorry but Anon's answer is not correct, at least according to &quot;Introduction to Algorithms, 3d Edition&quot; by Cormen. The binary search tree property says that there CAN be duplicates:

&quot;Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key = x.key.&quot;

In other words, the value of a child node may be equal to the value of a parent node, which would yield the result that &quot;Interview Candidate&quot; posted on Mar 14 2012. Performing an inorder tree walk would yield sorted nodes.

Matt on Mar 17, 2012
4

public static isValidBST(TreeNode root, MIN_INTEGER, MAX_INTEGER)
{
if (root == null) // children of leaf nodes
{
return true;
}

return root.data &gt;= INTERGER_MIN &amp;&amp; root.data &lt;= INTEGER_MAX &amp;&amp; isValidBST(root.left, INTEGER_MIN, root.data) &amp;&amp; isValidBST(root.right, root.data, INTEGER_MAX)
}

Long on Apr 20, 2012