Amazon Interview Question Software Engineer in Tests
I have a doubt in the question... The given tree is a BST... So if omit any 1 node... The BST still remains a BST. Why cant we return this tree as the solution. It is definitely a BST and it does contain the largest number of nodes
yeah it should be inorder, but preorder might be required to construct back the tree
1) find inorder I and preorder P O(n)
2) find longest continuos increasing subsequence from I O(n)
3) finding the root from the sequence using I and P. this is classic build tree using preorder/inorder.
node * ReturnMaxSubBst(node *root)
{
int lcount = count(root->left);
int rcount = count(root->right);
if(lcount >= rcount)
return isBst(root->left)?root->left:NULL;
else
return isBst(root->right)?root->right:NULL;
}
int count(node *root)
{
if (root == NULL)
return 0;
return( count(root->left) + 1 + count(root->right));
}
int isBst(node *root)
{
if(root == NULL)
return true;
if(root->left != NULL && min(root->left) > root->data)
return false;
if(root->right != NULL && max(root->right) <= root->data)
return false;
if(!isBst(root->left)&&!isBst(root->right))
return false;
return true;
}
node* min(node *root)
{
while(root != NULL)
root = root->left;
return root;
}
node* max(node *root)
{
while(root != NULL)
root = root->right;
return root;
}
I do not understand how this is a correct solution. There are several issues here -
1. Even when the size of the right subtree is greater than that of the left or vice versa, there is no guarantee that the largest BST is going to exist in right/left. It can be in either subtree.
2. After counting the # of nodes, it is simply checking from the root, which sub tree is actually a BST. It is not checking the subtrees of subtrees for BSTs.
If retirnMaxSubBST is recursively called for every node in the tree, only then can this solution work. Also, the function does not return the number of nodes in that tree either its root.
yeah what you said is correct , let me know if the following recursive program will work.
public Node LargestBST(Node currNode, Node maxNodeBST) {
if (currNode == null) {
return null;
}
boolean isBST = isBST(currNode);
int size = size(currNode);
int sizeOfMaxBst = size(maxNodeBST);
if (isBST && sizeOfMaxBst < size) {
maxNodeBST = currNode;
}
if (!isBST) {
maxNodeBST = LargestBST(currNode.getLeftPointer(), maxNodeBST);
maxNodeBST = LargestBST(currNode.getRightPointer(), maxNodeBST);
}
return maxNodeBST;
}
I got following sln, I think it is more neat. Basically the function return the BST size if the current sub tree is a BST, otherwise return -1. There are static parameters that save the max BST and its size.
class BTNode
{
public int val;
public BTNode left;
public BTNode right;
}
static int GetMaxBstSize(BTNode Node, ref BTNode MaxBst, ref int MaxBstSize)
{
int leftSize, rightSize, thisSize;
if (Node == null)
return 0;
leftSize = GetMaxBstSize(Node.left, ref MaxBst, ref MaxBstSize);
rightSize = GetMaxBstSize(Node.right, ref MaxBst, ref MaxBstSize);
if (leftSize < 0 || rightSize < 0)
return -1;
if ((Node.left != null && Node.left.val > Node.val) ||
(Node.right != null && Node.right.val < Node.val))
return -1;
thisSize = leftSize + rightSize + 1;
if (MaxBstSize < thisSize)
{
MaxBstSize = thisSize;
MaxBst = Node;
}
return thisSize;
}
The Solution is to find the Largest BST In a given BT , let me know if there is some thing wrong with the following code
public Node LargestBST(Node currNode, Node maxNodeBST) {
if (currNode == null) {
return null;
}
boolean isBST = isBST(currNode);
int size = size(currNode);
int sizeOfMaxBst = size(maxNodeBST);
if (isBST && sizeOfMaxBst < size) {
maxNodeBST = currNode;
}
if (!isBST) {
maxNodeBST = LargestBST(currNode.getLeftPointer(), maxNodeBST);
maxNodeBST = LargestBST(currNode.getRightPointer(), maxNodeBST);
}
return maxNodeBST;
}