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.

Interview Answer

4 Answers


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

Interview Candidate on Mar 14, 2012

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

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

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

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 "Interview Candidate" posted on Mar 14 2012. Performing an inorder tree walk would yield sorted nodes.

Matt on Mar 17, 2012

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

       return >= INTERGER_MIN && <= INTEGER_MAX && isValidBST(root.left, INTEGER_MIN, && isValidBST(root.right,, INTEGER_MAX)

Long on Apr 20, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.