## Ebay Interview Question for Software Engineer / Developers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
1
of 3 vote

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.

``````public boolean isBSTMain(Node root) {
return (isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE));
}

private boolean isBST(Node node, int min, int max) {
if (node == null)  return true;

if (node.data < min || node.data > max) return false;

// left should be in range min...node.data
boolean leftOk = isBST(node.left, min, node.data);
if (!leftOk) return false;

// right should be in range node.data..max
return isBST(node.right, node.data, max);
}``````

This solution is O(n)

Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
0

@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);
}``````

Comment hidden because of low score. Click to expand.
0

How to display double value double d = 999999999999999.99 in String format with the same value.

Comment hidden because of low score. Click to expand.
0

@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

Comment hidden because of low score. Click to expand.
0

it should be

boolean leftOk = isBST(node.left, min, node.data-1);
if (!leftOk) return false;

// right should be in range node.data..max
return isBST(node.right, node.data+1, max);
}

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````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)));
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

if a binary tree is a bst, an inorder traversal should return a sorted array...O(n) in both space and time...let me think if i can find something better

Comment hidden because of low score. Click to expand.
0
of 4 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

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);
}``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

The first line in the code should be
if(root==null) return true;

and not

if(root!=null) return true;

Comment hidden because of low score. Click to expand.
0

To pass the root->value in the top call as min,max parameters is WRONG. It should the lowest possible and the largest possible integer (tree's value type) values as it is done in the "coder"s comment on June 30, 2013.

Comment hidden because of low score. Click to expand.
0
of 2 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}
}``````

Comment hidden because of low score. Click to expand.
0

I think this should not work in case of this bst but yours will work:
-----3------
--2---- 5
1-4

Comment hidden because of low score. Click to expand.
0
of 0 vote

int a[20],i=0;
void check(struct treeNode *root)
{
struct treeNode *q=root;
if(q)
{
check(q->left);
a[i++]=q->data;
check(q->right);
}
else
return ;
}
int main()
{ check(root);
for(j=0;j<i-1;j++)
{
if(a[j]>a[j+1])
{
printf("not bst\n");
break;
}
}
if(j==i-1)
printf("bst\n");

Comment hidden because of low score. Click to expand.
0
of 0 vote

main idea is : left smaller and right bigger than parent.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

please explain the use of min and max in the above code??

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

Initially make
min=leftMostElement;
max=rightMostElement;

That serve the purpose

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````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);
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Python version:

``````def is_valid_bst(node):
previous_value = None
stack = []

while stack or node:
if node:
stack.append(node)
node = node.left
else:
node = stack.pop()
if previous_value > node.value:
return False
else:
previous_value = node.value
node = node.right

return True``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

Post order traverse should give us a sorted array.

Comment hidden because of low score. Click to expand.
0

Inorder traversal is the one that gives the values in sorted order...

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.