Amazon.com

www.amazon.com
Employer Engaged

Interview Question

Software Development Engineer Interview(Student Candidate) Atlanta, GA

Given any binary tree, write an method to test whether it

  is a Binary Search Tree
Answer

Interview Answer

1 Answer

1

bool isBinarySearchTree(Node* currNode)
{

 //
 // treat a NULL as an exception,
 // since you can't tell if an empty tree is a BST
 //
 if(!currNode)
 {
  throw MyException("got NULL");
 }

 bool isBST = true;

 //
 // check left, should be le (or null)
 //
 if(isBST && currNode->left)
 {
  if(currNode->left->value <= currNode->value)
  {
   isBST = isBinarySearchTree(currNode->left);
  }
  else
  {
   isBST = false;
  }
 }

 //
 // check right, should be gt
 //
 if(isBST && currNode->right)
 {
  if(currNode->right->value > currNode->value)
  {
   isBST = isBinarySearchTree(currNode->right);
  }
  else
  {
   isBST = false;
  }
 }

 return isBST;
}

JB on Oct 3, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.