Amazon Interview Question
SDE1sCountry: United States
Interview Type: Phone Interview
I suppose one could just attempt an in-order traversal as well, memoizing the previous node's key (k-1). If we encounter the situation that k-1 > k, then this cannot be a bst.
edit: Something like this, do the throw to terminate the test when the tree is not conforming
function traverse(node, cb) {
if (!node) {
return
}
traverse(node.left, cb)
cb(node)
traverse(node.right, cb)
}
function callback(node) {
if (k_minus_one && node.key <= k_minus_one) {
throw new Error("Not a BST")
}
k_minus_one = node.key
}
var k_minus_one
function isBinarySearchTree(root) {
try {
traverse(root, callback)
return true
} catch (e) {
return false
}
}
edit...reverse my comparator
Depth first search passing max and min values for a sub tree
//in C++
/*One issue is if root->value is MAX/MIN_INT but we can always create a special function for root and check in there...though a root at either extreme is going to make for a badly balanced tree
*/
bool isBinTree(node* node, int min=MIN_INT, int max=MAX_INT)
{
if(node==NULL)
return true; //node tree is a valid tree
if(node->value>=max || node->value <= min)
return false; //no duplicates allowed and must be in range
return isBinTree(node->left, min, this->value) &&
isBinTree(node->right,this->value,max);
}
#include <iostream>
namespace amazon {
template <class T>
struct binary_node
{
using value_type = T;
value_type value;
binary_node<T>* left;
binary_node<T>* right;
};
template <class T>
bool check_for_binary_search_tree(const binary_node<T>* root)
{
if (root->left && (root->left->value > root->value))
return false;
if (root->right && (root->right->value < root->value))
return false;
bool left_check = true, right_check = true;
if (root->left) left_check = check_for_binary_search_tree(root->left);
if (root->right) right_check = check_for_binary_search_tree(root->right);
return left_check && right_check;
}
} // namespace amazon
int main()
{
using type = int;
using node = amazon::binary_node<type>;
node* root = new node
{
8,
new node
{
3,
new node
{
1,
nullptr,
nullptr
},
new node
{
6,
new node
{
4,
nullptr,
nullptr
},
new node
{
7,
nullptr,
nullptr
}
},
},
new node
{
10,
nullptr,
new node
{
14,
new node
{
13,
nullptr,
nullptr
},
new node
{
15,
nullptr,
nullptr
}
}
}
};
std::cout << "Result: " << amazon::check_for_binary_search_tree(root) << std::endl;
return 0;
}
bool isBST(Node *root, int *prev)
{
if(root == NULL)
return true;
if(!isBST(root->left,prev))
return false;
if(prev >= root->data)
return false;
else
prev = root->data;
return isBST(root->right,prev);
}
int main()
{
int prev = INT_MIN
cout<<isBST(root, &prev);
}
You should check the binary tree property on the current node first, e.g. if a node has a value 5 and the left child of this node has the value 10, you want to return false immediately, there is no point in checking all of the subtree of 10 (which could be a BST coincidentally and also huge).
Simple Recursive method
isBST(Node *root)
{
bool l = r = true;
if( (root == NULL) || (root->left == NULL && root->right == NULL) )
return true;
if(root->left != NULL)
{
if(root->data > root->left->data)
l = isBST(root->left);
else
l = false;
}
if(root->right != NULL)
{
if(root->data < root->right->data)
r = isBST(root->right);
else
r = false;
}
return (l && r);
}
It is working fine for your given test-case.....
In this case function will return false.... Which is correct...
It doesn't work. In a binary search tree all the nodes in the left sub tree should be lesser than root, and all the nodes in the right sub tree are greater than root.
For the test case
3
2 5
1 4
The function is called using isBST(3)
which in turn calls
isBST(2) and isBST(5)(this is true)
now isBST(2) calls
isBST(1) and isBST(4) which is also true
so this method actually returns true.
See, at any point in each level of recursive call you don't have any information about the ancestors of that node. Hence there is no way you can say whether the tree is BST using this method.
Something on the lines of srterpe suggested. Use the inorder traversal (since the inorder traversal of a BST gives sorted numbers in ascending oprder) and compare the root with its left or right child for predecessor or successor respectively.
int isBST(struct node * root)
{
if(root)
{
if(root->left)
{
if(root->data > root->left->data)
{
isBST(root->left);
isBST(root->right);
}
else
return false;
}
else if(root->right)
{
if(root->data < root->right->data)
{
isBST(root->left);
isBST(root->right);
}
else
return false;
}
}
return true;
}
void main()
{.
.
if(isBST(root))
printf("\nIt is a BST!");
else
printf("\nIt is not a BST!");
.
.
}
public class BT<Key extends Comparable<Key>, Value> {
private Node root;
private class Node {
Key key;
Value value;
Node left, right, parent;
Node(Key k, Value v) {
key = k;
value = v;
}
}
public Value get(Key k) {
/* Add logic to retrive the value for a Key from the Tree */
}
public void put(Key k, Value v) {
/* Add logic to insert an element to the Tree */
}
private static boolean lessThan(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
//== Check if BT using In-Order traversal ==================================
private boolean checkBSTInorder(Node x, Key lastKey) {
if (x == null) return true;
checkBTInorder(x.left, lastKey);
if (lastKey != null && lessThan(x.key, lastKey))
return false;
else {
lastKey = x.key;
checkBTInorder(x.right, lastKey);
}
return true;
}
public boolean checkBSTInorder() {
if (root == null) return true; // empty tree - can be a BST.
return checkBTInorder(root, null);
}
//== Check if BT - alternative technique ==================================
private boolean checkBST(Node x) {
if (x == null) {
return true;
} else {
if (x.left != null && lessThan(x.key, x.left.key)) {
return false;
} else if (x.right != null && lessThan(x.right.key, x.key)) {
return false;
} else {
return checkBT(x.left) && checkBT(x.right);
}
}
}
public boolean checkBST() {
if (root == null) return true; // empty tree - can be a BST.
return checkBT(root);
}
//== Test Client ===========================================================
public static void main(String[] args) {
String[] a = { "L", "A", "M", "B", "N", "C", "O", "D", "P", "E", "Q", "F", "R", "G", "S", "H", "T", "U", "I", "V", "J", "W", "K", "X", "Z", "Y"};
BST<String, String> bt = new BST<>();
for (String x : a) {
bt.put(x, x); // Setting value same as key - but can be anything.
}
System.out.println("Is BST: " + bt.checkBST());
System.out.println("Is BST (using In-order traversal technique): " + bt.checkBSTInorder());
}
}
boolean isBST(Node root) {
if(root.left == null && root.right == null) return true;
//in Java, if A is false, then A && B doesn't evaluate B, therefore short circuits
if(root.right == null) return root.left.val < root.val && isBST(root.left);
if(root.right == null) return root.val < root.right.val && isBST(root.right);
return root.left.val < root.val && root.val < root.right.val && isBST(root.left) && isBST(root.right);
}
public class IsTreeBST {
public static void main(String[] args) {
NodeIsTreeBST temp = new NodeIsTreeBST();
temp = temp.NodeIsTreeBST(6);
temp.left = temp.NodeIsTreeBST(5);
temp.left.left = temp.NodeIsTreeBST(3);
temp.left.left.right = temp.NodeIsTreeBST(20);
temp.right = temp.NodeIsTreeBST(33);
temp.right.left = temp.NodeIsTreeBST(20);
temp.right.right = temp.NodeIsTreeBST(50);
System.out.println(isBST(temp, Integer.MIN_VALUE, Integer.MAX_VALUE));
}
public static boolean isBST(NodeIsTreeBST node , int min , int max) {
if(node == null)
return true;
if(node.data < min || node.data>max)
return false;
if(!isBST(node.left, min, node.data-1) || !isBST(node.right, node.data+1, max))
return false;
return true;
}
}
class NodeIsTreeBST {
int data;
NodeIsTreeBST left;
NodeIsTreeBST right;
public NodeIsTreeBST NodeIsTreeBST(int data) {
NodeIsTreeBST temp = new NodeIsTreeBST();
temp.data = data;
temp.left = null;
temp.right = null;
return temp;
}
}
//suppose treenode data is normal integer
bool JudgeBST(TreeNode *pTreeNode)
{
if(!pTreeNode) return true;
if(pTreeNode->leftchild && pTreeNode->rightchild){
return (pTreeNode->leftchild->data < pTreeNode->rightchild->data) &&
JudgeBST(pTreeNode->leftchild) && JudgeBST(pTreeNode->rightchild);
}else if(pTreeNode->leftchild){
return JudgeBST(pTreeNode->leftchild);
}else if(){
return JudgeBST(pTreeNode->rightchild);
}
return true;
}
bool is_bst(Node* n, Node* parent = null, bool left = true)
{
if (n == null) { return true; }
if (parent && left && n->value > parent->value) { return false; }
if (parent && !left && n->value < parent->value) { return false; }
return is_bst(n->left, n, true) && is_bst(n->right, n, false);
}
Recursively, by passing the current MIN and MAX down.
public class Solution {
public boolean isValidBST(TreeNode root) {
return isValidNode(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
private boolean isValidNode(TreeNode node, int min, int max) {
if (node == null)
return true;
if (node.val > max || node.val < min)
return false;
return isValidNode(node.left, min, node.val - 1) && isValidNode(node.right, node.val + 1, max);
}
}
Java Code :
public boolean isBinaryTree(BinaryNode node) {
if (flag == true) {
// Leaf Node
if (node.left == null && node.right == null) {
return flag;
}
else if (node.right != null && node.right.data >= node.data) {
isBinaryTree(node.right);
}
else {
flag = false;
}
if ((node.left != null && node.left.data < node.data)) {
isBinaryTree(node.left);
}
else {
flag = false;
}
}
return flag;
}
Depth first search passing max and min values for a sub tree
- Anonymous September 03, 2014