PayPal Interview Question Member Technical Staffs
Country: India
Interview Type: In-Person
This is a standard question, and that is the standard answer. Probably been there since before Boob dondero was born.
Why would there be a standard answer for this? The way Ajeet coded it looked very clean.
But true on the second point, any algorithm to check the invariant of a basic data structure isn't worth a "invented by Dr. ______" label.
Agreed. No need to invest further time on this if we can't gain anything in terms of space or time.
But a better implementation of classic algo is always needed.... :)
Actually we study these basic algos\DS since first day of our engineerig\science courses. So we use to these basic algorithms and we never think about second option to implement it.
I am using this algo (check BST) with same complexity since last three years but never think about this way (cleaner approach). We generally so much confident about basics that we dont think necessary to google it.
But if we use a complex\advanced data structure than we give it proper time to implement it. May be due to fear of complexity.
Just sharing my personal experience ....
3 years back I implemented BST with in half day (including all unit tests to verify boundaries etc).
But to implement a Suffix Tree take more than a week - excluding algo and complexity study ... :) I was already aware what algo i have to use ....I took this much time to try implementation with different approaches ... :)
Let root node of the given tree be r
Do a in-order traversal of the tree; determine if it is bst in the process by comparing node's key with the previous one; if less, false, else continue until traversal is finished, then true;
pseudo codes in java:
ArrayList a; //store the nodes
Boolean result=true;//assume it is BST
void inOrder(Node n){
if(n.left != null){
inOrder(n.left);
}
push(n, a)
if(n.right != null){
inOrder(n.right)
}
}
void push(Node n, ArrayList a){
if(n.key <= a.last){
result = false;
through exception;
}else{
a.add(n.key);
}
}
main(){
try{
inOrder(r);
}catch(exception e){
false;
}
true;
}
public class Node {
private Node left;
private Node right;
private int value;
public Node(Node left, Node right, int value) {
this.left = left;
this.right = right;
this.value = value;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
public int getValue() {
return value;
}
public boolean isBinarySearch(){
if(getLeft() != null && getRight() != null && getLeft().getValue() <= value && getRight().getValue() >= value) {
return true;
}
return false;
}
public static void main(String[] args){
Node eight = new Node(null, null, 8);
Node twelve = new Node(null, null, 12);
Node ten = new Node(eight, twelve, 10);
System.out.println(ten.isBinarySearch());
}
}
With such a definition of tree node:
struct BTreeNode
{
BTreeNode *left;
BTreeNode *right;
int value;
};
Here is solution:
bool isBinarySearchTree(BTreeNode *node)
{
if (node) {
bool leftOK = node->left ? (node->left->value < node->value) && isBinarySearchTree(node->left) : true;
bool rightOK = node->right ? (node->right->value > node->value) && isBinarySearchTree(node->right) : true;
if (!leftOK || !rightOK) return false;
}
return true;
}
Definition of BST is to contain *only unique values* in each node:
From wikipedia:
In computer science, a binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:
- The left subtree of a node contains only nodes with keys less than the node's key.
- The right subtree of a node contains only nodes with keys greater than the node's key.
- The left and right subtree each must also be a binary search tree.
- There must be no duplicate nodes.
Assume that this is the tree:
8
/ \
6 10
/\ /\
4 9 7 11
Code says this is BST, but it is not.
Excuse me? The common business (and only) scenario is to store unique values in each node. This is how all stuff works (sets, maps/dictionaries).
If you need store more same values (whatever value is) you put in each node structure container to store all these values.
If you would like to support same values in tree (it would not be a BST!) then in this case:
10
/ \
5 15
/ \
3 7
If you would like to put '5' one more time in the tree you would need to re-build all tree below existing 5 number. What business case requires such ineffective and slow way of storing things?
Krzysztof, let's calm down.
Your diagram above itself immediately gives the idea of how to insert duplicates just as easily as throwing them out or overwriting.
Just take the subtree rooted at 3, put it aside.
Put the new duplicate 5 where the 3 was.
Make the old subtree, the new left subtree of the new 5.
It is O(1) extra work over the regular insert and doesn't require you to "rebuild" all the tree below 5.
It seems (picture a tree), that everything works smoothly if we allow duplicates to to go on one side (like left).
That way when you search works fine still in lg(height).
And duplicates can be designed into most DSs and they are useful (Duplicate numbers in real data, same names "John Smith", etc. etc.).
Regular BST stuff seems perfectly easy to convert to add handling of duplicates.
For balanced BSTs, we could probably convert the rebalancing stuff for this to on our own. Or we google it. Wikipedia isn't the ultimate authority on everything possible and probable.
Now take you diagram above, change the 7 to a 11.
1) Is it still a BST?
2) What will your BSTcheck do for that test case?
Take care
Hi,
Well, I think anyway that common definition of whatever (in this case BST) is more than needed. In other case we can both be right even if we have completely opposit opinions on topic. Especially in computer science these definitions of things is our language. If it is not common there will be problems with understand each other.
To be consistent (at least in C++) it would be misleading to say that "set" can have non-unique values -> It is multiset. Every definition I found - and wikipedia seems to be right here - says that BST has only unique values.
(including Steven Skiena's "The Algorithm Design Manual"). If we do not follow definitions somebody can say you "Hey, your's solution does not allow duplicate values. Your solution is wrong!".
And of course algorithms written for BST will mostly work in BST-like (with duplicates) trees. But it is no more pure BST (at least for me ;-) ). No offense - just wanted clarify my point of view.
Thanks for finding bugs in my previous solution. Here is updated one (going from down to up of a tree):
bool isBinarySearchTree2(BTreeNode *node, int &min, int&max)
{
if (node)
{
int leftMin, leftMax, rightMin, rightMax;
bool leftOK = node->left ?
isBinarySearchTree2(node->left, leftMin, leftMax) && (min = leftMin, node->value > leftMax) : (min = node->value, true);
bool rightOK = node->right ?
isBinarySearchTree2(node->right, rightMin, rightMax) && (max = rightMax, node->value < rightMin) : (max = node->value, true);
if (!leftOK || !rightOK) return false;
}
return true;
}
BTW why somebody gave me minus for providing definition of BST from wikipedia... "somebody" - shame on you ! :-)
These points are dumb.
Can't even trade it in for free McDonalds burgers.
Going to create a new account just to get back down to 0.
+1 for good debate.
@ Krz,
I agree, anything can be anything.
Definitions are labels.
We need to move away from definitions and relying on them to write 6 word questions thus leading to multi-paragraph debates.
But yeah, if some random dude asked "What is a blah blah for BST?" I'd assume he meant the most basic form.
private static void checkBST(Node root) {
if(root .left!= null) {
if(root.value > root.left.value) {
checkBST(root.left);
} else {
System.out.println("Its not a BST");
}
} if(root .right!= null) {
if(root.value < root.right.value) {
checkBST(root.right);
} else {
System.out.println("Its not a BST");
}
}
}
As we all know that we can use IN-Order traversing for this, without using any extra space.
But the implementation of this by Bob Dondero is simply awesome:
private boolean isBST() { return isBST(root, null, null); } private boolean isBST(Node x, Key min, Key max) { if (x == null) return true; if (min != null && x.key.compareTo(min) <= 0) return false; if (max != null && x.key.compareTo(max) >= 0) return false; return isBST(x.left, min, x.key) && isBST(x.right, x.key, max); }Ref: leetcode.com/2010/09/determine-if-binary-tree-is-binary.html
- Ajeet October 23, 2013