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

Interview Answer

4 Answers

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

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

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

Long on Apr 20, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.