Amazon Interview Question for Development Support Engineers

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

``````//return true if BT with root=node is a BST
int isBST(struct node* node, int min, int max,int *count)
{
/* an empty tree is BST */
if (node==NULL)
return 1;

/* false if this node violates the min/max constraint */
if (node->data < min || node->data > max)
return 0;

*count++;
/* otherwise check the subtrees recursively,
tightening the min or max constraint */
return
( isBST(node->left, min, node->data-1) &&  // Allow only distinct values
isBST(node->right, node->data+1, max));  // Allow only distinct values
}

struct node* largestSubTree(struct node *root)
{
int count=0;
static int tmp_count=0;
static struct node *node=NULL;

if(!root) return NULL;

if(isBST(root,INT_MIN,INT_MAX,&count))
if(count>tmp_count)
{
tmp_count=count;
node=root;
return node;
}
largestSubTree(R->left);
largestSubTree(R->right);

return node;
}

//prints tree in pre order traversal
void printTree(struct node *root)
{
if(!root)
return;

cout<<root->data<<" ";
printTree(root->left);
printTree(root->right);
}

void main()
{
struct node *root=NULL,temp;
root=createTree(root); //tree is created

if((temp=largestSubTree(root))!=NULL)
{
cout<<"The largest sub-tree which is a binary tree is:\n";
printTree(root);
}
else
{
cout<<"Such subtree does not exist";
}
}``````

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

what is the need of count in isBST ?? Also, count argument is missing in return statement of isBST

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

I think you're on the right path, but there might a small thing you missed

In the LargestBST Method,

``````largestSubTree(R->left);
largestSubTree(R->right);``````

you return node but, you never actually compare the result of these two recursive calls. It should be something like

``````struct node* largestSubTree(struct node *root, int *count)
{
int countLeft = 0, countRight = 0;
static int tmp_count=0;
static struct node *node=NULL;

if(!root) return NULL;

if(isBST(root,INT_MIN,INT_MAX,&count))
if(count>tmp_count)
{
tmp_count=count;
node=root;
return node;
}
node* left = largestSubTree(R->left, &countLeft);
node* right = largestSubTree(R->right, &countRight);

if(countLeft > countRight)
node = left;
else
node = right;

return node;
}``````

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

A subtree is one that goes all the way till the leaves... a simple non-decreasing sequence for an inorder traversal need not necessarily point out the actual largest subtree.

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

using a recursive call: which get number of node, min, max for BST and return bool if this tree is a BST. Always rembmer the max number of node sub bst tree and root.
Anyway, this is a good question.

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

I think your way will work.

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

yes this is d right way.....Starting from root (and then left and right subtrees) we have to check whether the subtree is a BST or not (with the help of min and max values for the corresponding subtree......min=left-extreme-value & max=right-extreme-value)

At the same time if a BST subtree is found,we have to store no of nodes in this subtree and its root pointer in an array/linkedlist ......finally if we get more than 1 BST subtree,return the root pointer with maxm no of nodes.....
hope it helps.....a gud question indeeed!! :)

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

Use BFS technique and make a function which validate the BST property and return the MAX no of nodes in that BST

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

int LBST(node* n)
{
if( (n->left<n) && (n < n->right) && (LBST(n->left) != -1) && (LBST(n->right) != -1) )
return LBST(n->right) + LBST(n->left);

if(n->left==NULL && n->right ==NULL)
return 1;

else
return -1;

}

int maxNodes=0;
node* maxNode;

node* returnMaxBST(node* n)
{

int i=0;

if(n->left==NULL && n->right==NULL)
{
if(maxNodes==0)
{
maxNodes=1;
maxNode=n;
}

return n;
}

if(LBST(n) > maxNodes )
{
maxNodes=LBST(n);
maxNode = m;
}

returnMaxBST(n->left);
returnMaxBST(n->right);

return maxNode;;

}

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

int LBST(node* n)
{
if( (n->left<n) && (n < n->right) && (LBST(n->left) != -1) && (LBST(n->right) != -1) )
return LBST(n->right) + LBST(n->left);

if(n->left==NULL && n->right ==NULL)
return 1;

else
return -1;

}

-----------------------------------------------------------------------------------------------------

int maxNodes=0;
node* maxNode;

-----------------------------------------------------------------------------------------------------

node* returnMaxBST(node* n)
{

int i=0;

if(n->left==NULL && n->right==NULL)
{
if(maxNodes==0)
{
maxNodes=1;
maxNode=n;
}

return n;
}

if(LBST(n) > maxNodes )
{
maxNodes=LBST(n);
maxNode = m;
}

returnMaxBST(n->left);
returnMaxBST(n->right);

return maxNode;;

}

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

int LBST(node* n)
{
if( (n->left<n) && (n < n->right) && (LBST(n->left) != -1) && (LBST(n->right) != -1) )
return LBST(n->right) + LBST(n->left);

if(n->left==NULL && n->right ==NULL)
return 1;

else
return -1;

}

-----------------------------------------------------------------------------------------------------

int maxNodes=0;
node* maxNode;

-----------------------------------------------------------------------------------------------------

node* returnMaxBST(node* n)
{

int i=0;

if(n->left==NULL && n->right==NULL)
{
if(maxNodes==0)
{
maxNodes=1;
maxNode=n;
}

}

if(LBST(n) > maxNodes )
{
maxNodes=LBST(n);
maxNode = m;
}

maxNode= returnMaxBST(n->left);
maxNode= returnMaxBST(n->right);

return maxNode;

}

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

@giri
none of the 3 solutions you posted is working. post a proper solution.

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

I think the first answer itself gives a proper direction on solving this problem. People should read the responses before blindly providing crappy solutions.

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

Abe Dhakkan

If you think the first answer, as you said, "gives a proper direction on solving the problem," then you must have a solid understanding of the problem.

If that is true, then you should be able to provide an example data set plus the resulting data set from an algorithm.

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

Loda le!

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

Ok the first solution is partially right.change must be to find longest increasing sub string.Will longest increasing subseq work out???

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

Ragavenderan

I think the first solution is complete nonsense, it is not logically coherent and it is vacuous, but that may be just me.

You also seem to have a pretty good understanding of the problem.

Maybe you’re up to the challenge and you can provide an example data set plus the resulting data from an algorithm. If you understand this problem, that should be straight forward.

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

Michael, I agree that the solutions might be bullshit.

That does not mean the question is wrong.

Assume we need to implement the following method:

``````/// return max bst.
/// max is set to max value in the returned tree.
/// numNodes = number of nodes in the returned tree.
Tree * GetMaxBST(Tree * input, int * max, int *numNodes)``````

Can you think of a recursive method with this signature which will help you solve the problem?

Note a sub-tree is just a subset of connected nodes of the original tree.

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

Err.. make that

``````/// return max bst.
/// max is set to max value in the returned tree.
/// min is set to min value in the returned tree.
/// numNodes = number of nodes in the returned tree.
Tree * GetMaxBST(Tree * input, int * max, int *min, int *numNodes)``````

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

``````LOLer,

I strenuously disagree. The question is just plain and simply wrong, because it is not logically coherent, it just doesn't make any sense. It's conceivable that it could be clarified, but no one has volunteered to do that.

Your comment, at best, just further confuses the issue. Further your comment isn't even complete.

This class that you reference, Tree, which you conveniently did not define, is the heart of the problem. What is it? What are its data members? What kind of member functions does it have?

What no one seems to recognize is that not all Binary Trees are BSTs. Binary Trees and Binary Search Trees are two distinct classes of objects.

I'll repeat the definition of a BST that I posted earlier.

A BST is a finite set of nodes that is either empty or consists of a root and two disjoint Binary Search Trees called the left subtree and the right subtree. With the following properties:

1. The left subtree of a node contains only nodes with keys less than or equal to the nodes key.
2. The right subtree of a node contains only nodes with keys greater than the nodes key.
3. Both the left and right subtrees must also be Binary Search Trees.

This definition is why the problem statement, "given a binary tree, find the largest sub-tree which is a BST," is nonsensical.

I'll give you the same challenge that I have others. Please provide an example problem with the resulting BST that the algorithm would find. If the problem makes sense and you understand it, this should be trivial.

I patiently await you or anyone else who is up to this task.``````

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

Don't know why, but you can't read half of my response so I'm reposting it.

LOLer,

I strenuously disagree. The question is just plain and simply wrong, because it is not logically coherent, it just doesn’t make any sense. It’s conceivable that it could be clarified, but no one has volunteered to do that.

Your comment, at best, just further confuses the issue. Further your comment isn’t even complete.

This class that you reference, Tree, which you conveniently did not define, is the heart of the problem. What is it? What are its data members? What kind of member functions does it have?

What no one seems to recognize is that not all Binary Trees are BSTs, but all BSTs are Binary Trees. They are two distinct classes of objects.

I’ll repeat the definition of a BST that I posted earlier.

A BST is a finite set of nodes that is either empty or consists of a root and two disjoint Binary Search Trees called the left subtree and the right subtree. With the following properties:

1. The left subtree of a node contains only nodes with keys less than or equal to the nodes key.
2. The right subtree of a node contains only nodes with keys greater than the nodes key.
3. Both the left and right subtrees must also be Binary Search Trees.

This definition is why the problem statement, “given a binary tree, find the largest sub-tree which is a BST,” is nonsensical.

I’ll give you the same challenge that I have others. Please provide an example problem with the resulting BST that the algorithm would find. If the problem makes sense and you understand it, this should be trivial.

I patiently await you or anyone else who is up to this task.

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

Huh?

Consider the following tree:

``````10
/  \
2    15
\     \
4     7

This is a binary tree, whose max-subtree which is a BST is

10
/  \
2    15
\
4``````

Frankly, I think your objections are nonsensical...

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

LOLer,

Excellent, but the tree you’ve presented is a BST! Yes it is a Binary Tree, which is a Binary Search Tree, but any subtree is also going to be a BST.

You don’t have to test or further determine if any subtrees are BSTs, they are BSTs by definition.

Let’s look at the original problem statement.

“given a binary tree ,find the largest sub-tree which is a BST...(largest means subtree having largest no of nodes in it)”

So if we are working with BSTs and the problem is to find the largest subtree where largest means the largest no of nodes in it. Then the answer is trivial!
It is either the left subtree of the root or the right subtree of the root. The solution only requires you to count the number of nodes in the left and right subtrees and compare which is greater.

The following function will count the number of nodes in a BST.

``````struct Node {
int key;
Node* left;  // left subtree
Node* right; // right subtree
};

int CountNodes(Node* pNode)
{
if(pNode)
return CountNodes(pNode->left) + CountNodes(pNode->right) + 1;
else
return 0;
}

Node* FindMaxSubtree(Node* pNode)
{
if( CountNodes(pNode->left) >= CountNodes(pNode->right) )
return pNode->left; // left subtree is the largest
else
return pNode->right; // right subtree is the largest
}``````

In the example you’ve given, we have a tie, because the left subtree and the right subtree have the same number of nodes, 2.

From the problem statement your answer is incorrect, because it is not a subtree of the original tree.

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

Michael,

What are you talking about? Where did you get the statement "it must be either left sub-tree of right subtree" from? Perhaps that is where the confusion lies.

I interpret sub-tree as a sub-graph in the proper graph theoretical sense. Even if we mean sub-tree to include a node and all it's descendants (and other possible meaning), the question still makes sense. As any sub-tree of the left sub-tree (or right) is still a sub-tree...

The statement that a sub-tree is either the left one or the right is incorrect.

And, the tree i gave is not a BST, 7 isn't in the right place.

If we go by the second definition (including descendants of a node), the subtree

``````2
\
4``````

would be the answer in the example I gave.

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

Too many typos in my response, sorry. But I hope you get what I was trying to say.

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

Michael,

the question makes perfect sense.. LOLers example is not a BST. it is a BT.

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

LOLer,

You’re right, I missed that the 7 node was in the wrong place. This tree is a BST that has nodes that do not follow the properties of a BST and some nodes that do. I guess you could describe this as a BST that has errors?

At least with the example you’ve given, that makes some sense, like I said I’m probably just a bit dense and I don’t get it, fundamentally the question to me is just wacky. I've been looking at it with a black and white perspective, it either is a BST or it isn’t and why would you ever have anything else? Doesn’t really matter, because if the interviewer does think it’s valid then you’re left with justifying why it isn’t valid or doing your best to answer the question. The most reasonable thing to do is to give your best answer.

Still if the original poster had given an example like yours that would have made the intention of the problem clearer.

Regarding the issue of what a subtree means, (A subtree of a tree T is a tree comprised of a node in T and all of its descendants in T).

As you noted in your response, if you use that definition, the answer would then be:

2
\
\
4

But, exactly which definition of a sub-tree you would use could be clarified by the interviewer. Thanks again for your posting; this is finally making some sense to me.

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

LOLer,

So I have a candidate solution that appears to work correctly and returns the 2,4 sub-tree from your example and appears to return the correct result with other sample data. I don’t think this is the best solution, but I finally understand the problem and have a point to work from. It’s been fun!

``````template<class T>
bool IsBST(Node<T>* pNode, T min=INT_MIN,T max=INT_MAX)
{
if(!pNode) return true;
if(pNode->key < min || pNode->key > max) return false;
return (IsBST(pNode->l,min,pNode->key) && IsBST(pNode->r,pNode->key,max));
}

template<class T>
void FindBSTs(Node<T>* pRootNode, Node<T>*& pRootOfLargestBST, size_t& nodeCount)
{
if(!pRootNode) return;
if(IsBST(pRootNode))
{
size_t subTreeNodeCount = CountR<T>(pRootNode);
if(subTreeNodeCount > nodeCount )
{
nodeCount = subTreeNodeCount;
pRootOfLargestBST = pRootNode;
}
}
FindBSTs(pRootNode->l,pRootOfLargestBST,nodeCount);
FindBSTs(pRootNode->r,pRootOfLargestBST,nodeCount);
}

template<class T>
bool FindLargestBSTinBT(Node<T>*& pRootNode)
{
if(!pRootNode) return false;
Node<T>* pRootOfLargestBST=0;
size_t nodeCount=0;
FindBSTs(pRootNode,pRootOfLargestBST,nodeCount);
if(!nodeCount) return false;
pRootNode = pRootOfLargestBST;
return true;
}``````

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

@LOLer

``````10
/  \
2    15
\     \
4     7

This is a binary tree, whose max-subtree which is a BST is

10
/  \
2    15
\
4``````

In the above example

``````10
/  \
2    15
\
4``````

is not a subtree, since subtree is said to be rooted at some node and everything till leaves are considered. If u say subtree rooted at 10, then that will include all the nodes as its the root of the tree. If we say subtree rooted 2 then that will be as below:

``````2
\
4``````

So this example is wrong. But if we take the correct definition of subtree, then we have to go at each node and check if the subtree is BST or not. Amazon asks non sense questions, sometimes they ask some dummy design questions which have no meaning. I attended the interview once then decided that never join such a junk company. I think this question explains why Amazon interviewers are such junk guys with low IQ and knowledge. Basically a company where no one (atleast in India) knows to code in C++ is bound to contain mediocre java programmers and the result is these junk questions.

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

Is this qsn asking for subgraph or subtree..

If subtree, then we can do a dynamic algorithm solution. We can write a recursive isBST function, which takes a node and returns true or false

Pseudo Code:

Init count to 0s

Null Case.

if(!node->left && !node->right)
return true;
isBST(node->left, 2*i) and isBST(node->right, 2*i+1) and node->left->data < node->data <= node->right
count[i] = count[2*i] + count[2*i+1]

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

Anonymous,

I think you may be on the right track, but since you’ve only shown a fragment of the code, I’m not sure.

The term 2*i is the term you can use to find the left-child in a heap that is a complete binary tree and stored in an array where i is the array index. This makes me skeptical that you have a correct solution.

Maybe you can expand on your explanation?

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

I repeat the first approach does make sense. Have a look and make things clear to yourself
@Michael Jackson. Your argument is completely vacuous/illogical. First get your basics right. You seem to be loosing the basic definition/meaning of basic tree data structures. Brush up your basics and then come back here.
FYI: http://en.wikipedia.org/wiki/Binary_search_tree

HTH, Thank you.
I'm a big FAN of LOLer !

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

@Michael

The question is 100% correct,please do not argue pointlessly

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

Traverse the entire tree (using any traversal method) and pass each node (rather the binary subtree) to the following function isBST().

``````//Returns true if a binary tree is a binary search tree
bool isBST(NODE* tree, int min = INT_MIN, int max = INT_MAX)
{
if(!tree)
return false;

// Return false if this node violates the min/max constraint
if(tree->val < min || tree->val > max)
return false;

// Otherwise check the left and right subtrees recursively, updating the min or max constraints
return ( isBST(tree->left, min, tree->val) &&
isBST(tree->right, tree->val, max)
);
}``````

If the above function returns true, pass the same node to the following function count() to calculate the size (or the number of nodes) of this node (or the binary subtree).

``````//Function to calculate the size of a tree
int count(NODE* tree)
{
if(!tree)
return 0;
return (count(tree->left) + 1 + count(tree->right));
}``````

Now, store each node and its size in a data structure like a hashmap or an associative array. Then, the row in the hashmap with the highest size is the LARGEST SUBTREE WHICH IS A BST.

Complexity:
-----------
Traversal - O(n) for the given binary tree
Size calculation of each subtree - O(n) for each node(subtree).
Hashmap size - worst case space is O(n) if every subtree is a BST.
Scanning the hashmap for the highest size = O(1).

So, overall, this comes to O(n) complexity.

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

Traverse the entire tree (using any traversal method) and pass each node (rather the binary subtree) to the following function isBST().

``````//Returns true if a binary tree is a binary search tree
bool isBST(NODE* tree, int min = INT_MIN, int max = INT_MAX)
{
if(!tree)
return false;

// Return false if this node violates the min/max constraint
if(tree->val < min || tree->val > max)
return false;

// Otherwise check the left and right subtrees recursively, updating the min or max constraints
return ( isBST(tree->left, min, tree->val) &&
isBST(tree->right, tree->val, max)
);
}``````

If the above function returns true, pass the same node to the following function count() to calculate the size (or the number of nodes) of this node (or the binary subtree).

``````//Function to calculate the size of a tree
int count(NODE* tree)
{
if(!tree)
return 0;
return (count(tree->left) + 1 + count(tree->right));
}``````

Now, store each node and its size in a data structure like a hashmap or an associative array. Then, the row in the hashmap with the highest size is the LARGEST SUBTREE WHICH IS A BST.

Complexity:
-----------
Traversal - O(n) for the given binary tree
Size calculation of each subtree - O(n) for each node(subtree).
Hashmap size - worst case space is O(n) if every subtree is a BST.
Scanning the hashmap for the highest size = O(1).

So, overall, this comes to O(n) complexity.

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

i think this is a valid solution, basically a combination of two problems: verifyBST + tree size

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

Sounds like it should work, but I think part of the challenge is how you can combine the BST verification and the counting into a single function so that you won't have to traverse a subtree twice.

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

here is what i think mostly will work. Not well tested but i am sure can be achieved with something like this -

take 2 buckets to store temp and max BST and 1 stack

if(start == null)
return

push start to temp
if(start->left != null)
if start->left < start
push to temp bucket
go to step 1 with start = start->left
else push start->left to stack

if(start->right != null)
if start->right > start,
push to temp bucket
go to step 1 with start = start->right
else push start->right to stack

compare temp with max and if required, update max
assign start to stack.pop and start from beginning

//idea is to store captured BST from current node and compare it with Max
if you find BST from current node and its broken somewhere down the road,
you can't find bigger BST from one of its child EXCEPT that BST starts from
or sub tree of broken node. so dont visit all child of start but only visit broken nodes so store them on stack.

-------15----
| |
------16------ 14
| |
8 32
-------- -----
| | |
5 4 30

so here 16 and 14 both goes to stack on first run. Max = 15
pop 16, and you will end up with temp = 16,8,5,32,30 and 4 going on stack. update max.
pop 14. temp = 14. no need to update max.
pop 4. temp = 4. no need to update max.

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

Example graph did not go through well.

``````-------15----
|            |
------16------     14
|            |
8            32
--------    -----
|      |    |
5      4    30``````

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

{ }

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

In-order traversal of binary tree, and then find largest non-decreasing sequence, start index of this sub-sequence is the root of BST.

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

Call below method recursively for each left & right subtree of original tree. Return as soon as isBST returns true with root at the iteration

/*
Returns true if the given tree is a BST and its
values are >= min and <= max.
*/
int isBSTUtil(struct node* node, int min, int max) {
if (node==NULL) return(true);

// false if this node violates the min/max constraint
if (node->data<min || node->data>max) return(false);

// otherwise check the subtrees recursively,
// tightening the min or max constraint
return
isBSTUtil(node->left, min, node->data) &&
isBSTUtil(node->right, node->data+1, max)
);
}

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

I don't really see any size comparisons here. What if there's a BST somewhere below the left child and another BST somewhere below the right child. How will you determine which one is bigger?

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

As the first solution did half the work.

Do in order traversal of the tree .(Store the result we need it again)
Find the longest non-decreasing sequence .
Now the starting element is the root.
Now do inorder traversal on that tree if it again becomes non decreasing (i.e check isBST )then we arrived at the answer
else
go to next longest non-decresing substring and repeat the check for isBST?

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

``````int largestBST(node *root, int *min, int *max, node **sub, int *max_size)
{
if (root == NULL)
{
/* Initializing min and max if we hit a leaf node */
*min = INT_MAX;
*max = INT_MIN;
return 0;
}

int isbst;

/* l_size is the size of the left subtree */
int l_size = largestBST(root->left, min, max, sub, max_size);

/* If it is a leaf node we set currMin to root->data else
we set currMin to minimum of left subtree */
int currMin = (l_size == 0) ? root->data : *min;

if (root->data < *max )
isbst = 0;

int r_size = largestBST(root->right, min, max, sub, max_size);
int currMax = (r_size==0) ? root->data : *max;

if (root->data > *min )
isbst = 0;

if (isbst) {
if (l_size + r_size  + 1 > *max_size ) {
*max_size = l_size + r_size  + 1;
*sub = root;
}
*min = currMin;
*max = currMax;
return l_size + r_size +1;
}
return -1;
}``````

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

We can do it by keeping track if every node in the tree is a valid BST root, and the number of children it has. We can do this by doing a Depth First Traversal in O(v) time and updating all of the counts and keeping track of a global max variable.

Assuming a nice node class,

``````class node {
public:

bool isValidBSTRoot;
int treeSize;

int value;

node *left;
node *right;

node(int val) {
value = val;
left = NULL;
right = NULL;
isValidBSTRoot = false;
}
};``````

And a couple of global variables (can be done without them, but this makes it easy),

``````int maxTreeSize = 0;
int maxTreeRoot = 0;``````

The code that actually figures out the answer,

``````// recursive DFS, updating isValidBSTRoot and treeSize whenever a node finishes
void findBiggestBST(node *root) {
if (root == NULL)
return;

findBiggestBST(root->left);
findBiggestBST(root->right);

// Make sure both children are BSTs
root->isValidBSTRoot = (!root->left || root->left->isValidBSTRoot) && (!root->right || root->right->isValidBSTRoot);

// Make sure children aren't in the wrong order
if (root->left && root->left->value > root->value)
root->isValidBSTRoot = false;
if (root->right && root->right->value < root->value)
root->isValidBSTRoot = false;

// No reason to bother updating and checking counts if we're not a valid BST root
if (!root->isValidBSTRoot)
return;

// Count ourself
root->treeSize = 1;

// Count number of left children if we have a left child
if (root->left)
root->treeSize += root->left->treeSize;

// Count number of right children if we have a right child
if (root->right)
root->treeSize += root->right->treeSize;

// Check to see if we're the new max
if (root->treeSize > maxTreeSize) {
maxTreeSize = root->treeSize;
maxTreeRoot = root->value;
}
}``````

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

@LOLer

``````10
/  \
2    15
\     \
4     7

This is a binary tree, whose max-subtree which is a BST is

10
/  \
2    15
\
4``````

In the above example

``````10
/  \
2    15
\
4``````

is not a subtree, since subtree is said to be rooted at some node and everything till leaves are considered. If u say subtree rooted at 10, then that will include all the nodes as its the root of the tree. If we say subtree rooted 2 then that will be as below:

``````2
\
4``````

So this example is wrong. But if we take the correct definition of subtree, then we have to go at each node and check if the subtree is BST or not. Amazon asks non sense questions, sometimes they ask some dummy design questions which have no meaning. I attended the interview once then decided that never join such a junk company. I think this question explains why Amazon interviewers are such junk guys with low IQ and knowledge. Basically a company where no one (atleast in India) knows to code in C++ is bound to contain mediocre java programmers and the result is these junk questions.

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

Lets divide this to sub problems.
1. Given a binary tree find out if its a BST. -- isTreeBST()
2. Given a tree find total number of nodes -- getTotalObjects()
3. Finally find larget BST using recusrion - getLargestBST().

Code :

``````public Tree<T> getLargestBST(){
if(isTreeBST())return this;
else {int l = 0;
if(lTree!=null){
l = lTree.getLargestBST().getTotalObjects();
}
int r = 0;
if(rTree!=null){
r = rTree.getLargestBST().getTotalObjects();
}
if(l>r) return lTree.getLargestBST();
else return rTree.getLargestBST();
}
}

public boolean isTreeBST(){
if(root == null) return true;
boolean l = true;
boolean r = true;
if(lTree != null) {
if(lTree.root.compareTo(root)<0) {
l = lTree.isTreeBST();
}else{
return false;
}
}
if(rTree != null) {
if(rTree.root.compareTo(root)>0) {
r = rTree.isTreeBST();
}else{
return false;
}
}
return l&&r;
}

public int getTotalObjects(){
int n = 0;
if(root!=null) n++;
if(lTree!=null){
n +=lTree.getTotalObjects();
}
if(rTree!=null){
n +=rTree.getTotalObjects();
}
return n;
}``````

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

I have a solution of O(n) (linear in the number of nodes).
The basic approach is command and conquer (and from bottom to top) - I use recursion to start from the leaves and continue to count nodes as long as my merge of each two nodes and their parent results in having a legal BST (on my way up).

Java code:

``````public static Result getMaxNodesBst(Node<Integer> root) {
if (root == null) {
return null;
}
if (isLeaf(root)) {
return new Result(root, 1);
}
Result res = new Result(null, 0);
getNodeInfo(root, res);
return res;
}

private static NodeInfo getNodeInfo(Node<Integer> n, Result res) {
if (n == null) {
return NodeInfo.empty();
}
if (isLeaf(n)) {
return new NodeInfo(n.getKey(), n.getKey(), 1);
}
NodeInfo leftSubTree = getNodeInfo(n.getLeft(), res);
NodeInfo rightSubTree = getNodeInfo(n.getRight(), res);
return merge(n, leftSubTree, rightSubTree, res);

}

private static NodeInfo merge(Node<Integer> parent, NodeInfo leftSubTree, NodeInfo rightSubTree, Result result) {

if (parent.getKey() > leftSubTree.max && parent.getKey() < rightSubTree.min) {
Integer currMax = leftSubTree.numOfNodes + rightSubTree.numOfNodes + 1;
if (currMax > result.maxNumOfNodes) {
result.node = parent;
result.maxNumOfNodes = currMax;
}
return new NodeInfo(rightSubTree.isEmpty() ? parent.getKey() : rightSubTree.max, leftSubTree.isEmpty() ? parent.getKey() : leftSubTree.min,
currMax);
}
return NodeInfo.na();
}

private static boolean isLeaf(Node<Integer> root) {
return root.getLeft() == null && root.getRight() == null;
}

private static class NodeInfo {

static final NodeInfo empty = new NodeInfo(Integer.MIN_VALUE, Integer.MAX_VALUE, 0);
static final NodeInfo na = new NodeInfo(Integer.MAX_VALUE, Integer.MIN_VALUE, -1);

Integer max;
Integer min;
Integer numOfNodes;

public NodeInfo(Integer max, Integer min, Integer depth) {
this.max = max;
this.min = min;
this.numOfNodes = depth;
}

public boolean isEmpty() {
return numOfNodes == 0;
}

public static NodeInfo na() {
return na;
}

public static NodeInfo empty() {
return empty;
}

private boolean isNa() {
return this.numOfNodes == -1;

}
}

static class Result {
private Node<Integer> node;
private Integer maxNumOfNodes;

public Result(Node<Integer> node, Integer maxDepth) {
this.node = node;
this.maxNumOfNodes = maxDepth;
}

public Integer getMaxDepth() {
return maxNumOfNodes;
}

public Node<Integer> getNode() {
return node;
}
}``````

And some Unit test:

``````@Test
public void test() {
BinarySearchTree<Integer> t1 = new BinarySearchTree<>(new Node<>(5, null, null));
Assert.assertEquals(Integer.valueOf(1), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
Assert.assertEquals(Integer.valueOf(2), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
Assert.assertEquals(Integer.valueOf(3), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
Assert.assertEquals(Integer.valueOf(4), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
Assert.assertEquals(Integer.valueOf(5), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
Assert.assertEquals(Integer.valueOf(6), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
Assert.assertEquals(Integer.valueOf(7), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
Assert.assertEquals(Integer.valueOf(8), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
t1.getRoot().setKey(100);
Assert.assertEquals(Integer.valueOf(4), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
t1.getRoot().getRight().getRight().setKey(6);
Assert.assertEquals(Integer.valueOf(3), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
}``````

Note that BinarySearchTree and Node are my own implementations.

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

In-order traversal of binary tree, and then find largest non-decreasing sequence, start index of this sub-sequence is the root of BST.

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

find start index of longest non-decreasing sequence obtained by in-order

use this index to find the root of BST in preorder traversal of tree

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

This question is nonsensical to me. I’ll parse it out and explain what I find confusing.

"Given a binary tree"

Ok got that. My understanding is a binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree.

"Find the largest subtree which is a BST…(largest means subtree having largest no of nodes in it)"

By definition any subtree is going to be a binary tree, so WTF does this questioner mean by a subtree which is a BST?

Let’s look at a definition for a Binary Search Tree (BST). A BST is a finite set of nodes that is either empty or consists of a root and two disjoint Binary Search Trees called the left subtree and the right subtree. With the following properties:

(1. The left subtree of a node contains only nodes with keys less than or equal to the nodes key.)
(2. The right subtree of a node contains only nodes with keys greater than the nodes key.)
(3. Both the left and right subtrees must also be Binary Search Trees.)

So the root cause of my confusion with this question is the discordance between starting apparently with a Binary Tree and then referring to its subtrees as Binary Search Trees. It’s either a Binary Search Tree or a Binary Tree. It doesn’t make any sense that it is both, or this is a data structure that I’m not familiar with. If that is the case the questioner should have explained in detail what they meant.

Some of the proposed answers are the following:

“Use BFS technique and make a function which validate the BST property and return the MAX no of nodes in that BST”

“using a recursive call: which get number of node, min, max for BST and return bool if this tree is a BST. Always rembmer the max number of node sub bst tree and root. Anyway, this is a good question.”

WTF does it mean to validate the BST property or return bool if this tree is a BST, that’s inherent in the very definition of the data structure itself. Again, it either has it or it doesn’t. It’s not something you have to validate.

So apparently I’m not the only one confused by this question.

I don’t believe any of the proposed answers make any sense, and I don’t think any of the responders understand the simple definition of a Binary Search Tree, or the distinction between a Binary Tree and Binary Search Tree. I don’t know it all and I could be wrong, so if some enlightened soul feels they have parsed this question correctly, please speak up.

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

It is a perfect valid question.

Binary tree: a tree where each node at at most 2 children.

Binary search tree: A Binary tree with keys attached to nodes, satisfying the property you state.

So given a binary tree with keys attached to node, find the largest subtree, whose keys from a binary search tree.

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

Abe Dhakkan,

After reading your response and thinking about this question some more I must say that what I find even more confusing than the question itself is the confusing answers that are given which for the better majority make no freaking sense at all.

So if you understand the question and it is perfectly valid to you, then what would be most useful is if you provided an algorithm or code that resolves the question.

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

The question is perfectly valid.. He is not asking if the entire is a BST or not. Hes asking if any subtree is.

Every BST is a binary tree, but every Binary tree isnt a BST.

Think of it recursively..

Each node has a tree rooted at its left child and right child.

The question asks if such a tree is a binary search tree..

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

use dynamic programming...

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.