Amazon Interview Question Software Engineer / Developers
0of 0 votesfind BST of max size in a binary tree
public static void maxBSTSize(BiTree t){
Pair p = maxBSTsizeHelper(t, 0);
System.out.println(p.max);
}
public static Pair maxBSTsizeHelper(BiTree t, int max){
Pair p = new Pair();
if(t==null){
p.max = max;
p.current = 0;
return p;
}
else{
Pair left;
Pair right;
p.current = 1;
left = maxBSTsizeHelper(t.left, max);
right = maxBSTsizeHelper(t.right, max);
if(t.left!=null && t.Node >= t.left.Node){
p.current = p.current + left.current;
}
if(t.right!=null && t.Node < t.right.Node){
p.current = p.current + right.current;
}
p.max = Math.max(left.max, right.max);
p.max = Math.max(p.max, p.current);
}
return p;
}
public static void main(String args[]){
BiTree t = new BiTree(10, new BiTree(15, new BiTree(22, null, null), new BiTree(7, null, null)), new BiTree(18, new BiTree(17, null, null), new BiTree(77, null, null)));
maxBSTSize(t);
}
Basicly the idea is the following:
At each node, we produce the size of the BST with root as current node.
For this:
1) the current node contributes to the size as 1.
2) we check if the left branch contributes and add the size from there (recursive step)
3) we check if the right branch contributes and add the size from there (recursive step)
4) we then compare the size of the BST rooted at the current node with the max. sized BSTs of the left and right branch.
5) we return two items:
a) the size of the BST with current node as root
b) the size of the largest BST found as a subtree of the tree with current node as root
One correction (altough the code does work without this correction): the "max" parameter to recursive call is unnecessary and the base case (null node) should be the following:
if(t==null){
p.max = 0;
p.current = 0;
return p;
}
the input is a binary tree (need not to be a bst).
it need to satisfy two conditions:
left <= parent <right and min < left,right<max. the min and max values will come from the ancestors. for root min and max are -infinity and +infinity. then for left tree -->min is -infinity,max is root.value. and for right tree --> min is root.value,max is +infinity.
Now we can compute the max BSt by returning the nodes in tree which are BST. the magnitude (+/-) will indicate the bst relationship status.
Steps:
1. Create inorder array for the entire tree.
2. Now Find the longest sorted contiguous sub-sequence in the Array
1. Keep an auxiliary array of the size of the original array and initialize it with zeros. The i’th element of this array holds the number of elements which are in sorted order after index i in the original Array.
2. Traverse the original Array from right to left
if(original[i] < original[i+1])
auxiliary[i] = auxiliary[i+1] + 1;
3. Find the maximum element in the Auxiliary array and print the elements ahead of that index from the original array.
consider : 3(5(4)(6)))(8(9)(10)).
inorder traversal will give:
34569810. taking longest subseq will give:34569 which is not a bst(as 8(9)(10) is not a bst).
int findbst(node *tree)
{
if(tree==NULL)
return 0;
if(isBST(tree))
return size(tree));
if((tree->left->data < tree->data) && (tree->data < tree->right->data))
return (1+findbst(tree->left)+findbst(tree->right))
else if((tree->left->data < tree->data) && (tree->right->data < tree->data))
return (max(1+findbst(tree->left),findbst(tree->right))
else if((tree->left->data > tree->data) && (tree->right->data > tree->data))
return (max(findbst(tree->left),1+findbst(tree->right))
else
return (max(findbst(tree->left),findbst(tree->right))
}
Correct me if it is wrong!!!!
Inorder traversal of the tree, put the values in an array. Now find the longest increasing subsequence in array
Just calculating all possible BST sizes Any better solution?
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define MAX_INT 32700
#define MIN_INT -32700
struct treeNode
{
int data;
bool isRootOfBST;
struct treeNode* left;
struct treeNode* right;
};
//Utility Function
treeNode* createNode(int data)
{
treeNode* newNode = (treeNode*)malloc(sizeof(treeNode));
newNode->data = data;
newNode->isRootOfBST = false;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
//Utility Function
void printInOrder(treeNode* root)
{
if(!root) return;
printInOrder(root->left);
printf("%d ", root->data);
printInOrder(root->right);
}
bool isBST(treeNode* root, int min, int max)
{
if(!root) return true;
bool bst = false;
if(min <= root->data && root->data < max) bst = true;
return isBST(root->left, min, root->data) && isBST(root->right, root->data, max) && bst;
}
//Returns the number of nodes in the maximum BST
int maxBST(treeNode* root)
{
if(!root) return 0;
int leftMax = 0;
int rightMax = 0;
if(root->left) leftMax = maxBST(root->left);
if(root->right)rightMax = maxBST(root->right);
if(isBST(root, MIN_INT, MAX_INT)) return 1+leftMax+rightMax;
else return (leftMax<rightMax)?rightMax:leftMax;
}
int main()
{
treeNode* root = createNode(18);
root->left = createNode(47);
root->right = createNode(10);
root->left->left = createNode(54);
root->left->right = createNode(30);
root->left->right->left = createNode(28);
root->left->right->left->left = createNode(7);
root->left->right->left->right= createNode(29);
root->right->left = createNode(11);
root->right->right = createNode(13);
root->right->left->left = createNode(4);
printInOrder(root); printf("\n");
printf("%d ", maxBST(root));
}
time complexity o(n2) space o(n)
- Anonymous August 29, 2010public static void main(String[] args) {
Tree root = newNode(10);
Tree n1 = newNode(15);
Tree n2 = newNode(22);
Tree n3 = newNode(7);
Tree n4 = newNode(18);
Tree n5 = newNode(17);
Tree n6 = newNode(77);
root.left = n1;
root.right = n4;
n1.left = n2;
n1.right = n3;
n4.left = n5;
n4.right = n6;
List<Tree> l = levelOrderTrav(root);
System.out.println("Size : " + l.size());
System.out.println("largest size BST in given BT: " + getLargestBSTInBT(l));
}
private static List<Tree> levelOrderTrav(Tree root){
List<Tree> l = new ArrayList<Tree>();
if(root == null){
return l;
}
Queue<Tree> q = new LinkedList<Tree>();
q.add(root);
while(!q.isEmpty()){
Tree n = q.poll();
l.add(n);
if(n.left!=null){
q.add(n.left);
}
if(n.right!=null){
q.add(n.right);
}
}
return l;
}
private static int getLargestBSTInBT(List<Tree> l){
int len =0;
int i=0;
int size = l.size();
int tempLen =0;
for(i=0;i<size;i++){
Queue<Integer> q = new LinkedList<Integer>();
q.add(i);
tempLen =1;
while(!q.isEmpty()){
int j = q.poll();
if(2*j+1 < size){
if(l.get(2*j+1).data<l.get(j).data){
tempLen++;
q.add(2*j+1);
}
}if(2*j+2 < size){
if(l.get(2*j+2).data>= l.get(j).data){
tempLen++;
q.add(2*j+2);
}
}
}
if(tempLen>len){
len = tempLen;
}
}
return len;
}