Ebay Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
Correct me if I'm wrong, I think this would not work for the below case. The correct approach to this problem is the one posted by vgeek.
---------------------------5
-------------3 10
--------------------------11
PS: Forgive me for the poor tree structure.
Basically 5 is root of the with 3 as left child (3 has 11 as right child) and 10 as right child.
@arun_lisieux it works buddy, but don't take my word for it, here is a unit test, go ahead and test it yourself.
@Test
public void testIsBST() {
Node root = new Node(5);
root.left = new Node(3);
root.right = new Node(10);
root.left.right = new Node(11);
boolean bst = isBST(root);
assertEquals(false, bst);
}
How to display double value double d = 999999999999999.99 in String format with the same value.
@arun
that is an invalid BST as the value 11 should be the right child of 10, not of 3 - it would never be inserted in that position
bool isBST(Node root) {
return isBSTNode(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
}
bool isBSTSubTree(Node node, int minValue, int maxValue) {
return (node == null ||
(node.value > minValue
&& node.value < node.maxValue
&& isBST(node.left, minValue, node.value)
&& isBST(node.right, node.value, maxValue)));
}
Earlier I used to say if each element is greater/equal to it's left element and less/equal to it's right element this it's a BST. But in this approach the major flow is it does not take ancestors into considerations. This I learnt from this forum itself and found the below mentioned solution (not able to locate the original thread):
Solution: For a given node, all nodes in its left subtree should be less than or equal to this element and all nodes in its right subtree should be greater than or equal to this element. Here is the code for it:
IsBST(root, root->value, root->value);
boolean isBST(Node* root, Integer min, Integer max) {
if (root != null) {
return (min <= root->value <= max) && IsBST(root->left, min, root->value) && IsBST(root->right, root->value, max);
}
return true;
}
This is a good solution : O(n) time complexity and O(1) space if not consider the stack call, in stead of the InOrder solution which uses O(n) time and O(n) space.
Here is the java version:
public static boolean isBst(TreeNode root, int min , int max){
if(root==null) return true; //modified
if(root.d < min || root.d >max) return false;
return isBst(root.left, min, root.d-1) && isBst(root.right, root.d+1, max);
}
Nice one Mario, it is better than my solution and Kamy you are right if we ignore the call stack memory consumption in will be O(1) space algorithm but even if we consider the call stack memory the worse case memory will be 2*log(n) when recursing through a leaf node (for a balanced tree assuming the 2 int params of max and min) which makes it O(log n) space still better than inorder traversal for all n > 2, But even this can be reduced by senfing the pointers to the actual min node and max node rather than the data in it.
The first line in the code should be
if(root==null) return true;
and not
if(root!=null) return true;
Use inorder traversal. Keep a static pointer that is previous that points to the previous node.Note inorder traversal will lead to you a sorted set of values.If at any time current value is less than the previous value then it is not a bst otherwise it is:
#include <stdio.h>
#include <stdlib.h>
typedef struct node node_t;
struct node
{
int data;
node_t *left;
node_t *right;
};
node_t *newNode(int data)
{
node_t *nn=(node_t *)malloc(sizeof(node_t));
nn->data=data;
nn->left=NULL;
nn->right=NULL;
}
int isBst(node_t *root)
{
static node_t *prev=NULL;
if(root)
{
if(!isBst(root->left))
return 0;
if(prev!=NULL&&root->data<=prev->data)
return 0;
prev=root;
return isBst(root->right);
}
return 1;
}
int main()
{
node_t *root = newNode(4);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(3);
if(isBst(root))
printf("Is BST");
else
printf("Not a BST");
return 0;
}
Simple recursive call to each of the nodes to check if the left subtree is less than equal to Current Node and right subtree is greater than equal to current node.
class BinaryTree {
private class Node {
int value;
Node leftChild;
Node rightChild;
public Node(int val) {
value = val;
leftChild = null;
rightChild = null;
}
}
Node root = null;
private bool checkBST(Node currNode) {
if(currNode == null) return true;
else if(currNode.leftChild == null && currNode.rightChild == null) return true;
else {
if(currNode.leftChild != null && currNode.rightChild != null)
return( currNode.value >= currNode.leftChild.value
&& currNode.value <= currNode.rightChild.value
&& checkBST(currNode.leftChild)
&& checkBST(currNode.rightChild));
if(currNode.leftChild != null && currNode.rightChild == null)
return( currNode.value >= currNode.leftChild.value
&& checkBST(currNode.leftChild)
&& checkBST(currNode.rightChild));
if(currNode.leftChild == null && currNode.rightChild != null)
return( currNode.value <= currNode.rightChild .value
&& checkBST(currNode.leftChild)
&& checkBST(currNode.rightChild));
return false;
}
return false;
}
public void isBST() {
if(checkBST(root))
System.out.println("The BT is BST");
else
System.out.println("The BT is not BST");
}
}
a BST has minimum element in the leftmost .. & maximum in the right most ...... just take these two and
just check min < element in the tree <max
public boolean isBST() {
if (root == null) {
return true;
}
//initialize min
TreeNode ptr = root;
while(ptr.left != null){
ptr = ptr.left;
}
Integer min = ptr.element;
//initialize max
ptr = root;
while(ptr.right != null){
ptr = ptr.right;
}
Integer max = ptr.element;
return isBST_helper(root, min, max);
}
private boolean isBST_helper(TreeNode node, Integer min, Integer max) {
if (node == null)
return true;
if (node.element > max || node.element < min) {
return false;
}
return isBST_helper(node.left, min, node.element - 1)
&& isBST_helper(node.right, node.element + 1, max);
}
You need to use the definition of BST, i.e., the left node is smaller and the right node is bigger than the parent node, and traverse the tree to check if that condition satisfies.
This solution is O(n)
- oOZz June 14, 2013