CareerCup

It would be nice if you could just do a pre-order traversal, and count the number of nodes that you encounter that are in order, together. A nice, O(n) solution. But it won't work; you could have a big BST eg on the left, the root happens to be larger than all the left side (so it's still in order), and then the left-most node of the right tree is in-order too, by chance. But the rest of the right tree is not sorted. Our longest sequence found this way thus isn't a BST.

Is a 'subtree' defined as perforce including the leaves? If so it's pretty easy I think:

If you're a leaf, you're a (trivial) BST, return 1, and your value (a tuple, somehow). if you're a left tree, return the value of your right-most (largest) child, as well (if a right child-tree, return the value of the left-most child). Now, our max-subtree routine can do: if my left subtree is giving non-zero for BST size, and its biggest child is < my own value, and my right subtree is non-zero for BST size, and its left-most value is > my own, well, add the two sizes together, + one for myself, and return that BST size. Otherwise return 0 (if we're not a sub-BST, it doesn't matter what our largest/smallest children are). I guess you'd keep a global max-BST size seen so far variable, and print that at the end.

If you can have 'interior-only' BSTs, ie the interior nodes are ordered but some of the leaves are not, I think it'd have to be some dynamic programming thing.

Algo
1. Store number of nodes in a subtree in its data field.
2. Do inorder traversal and at each node sum up the nodes in left subtree+right sub tree+1.

int node_method(node* x)
{
x.data=1;
if(x.left==null && x.right== null)
return 1;

if(x.left!=null)
x.data+=node_method(x.left);

if(x.right!=null)
x.data+=node_method(x.right);

return x.data;
}

Complexity is O(n)
search node with max value of x.data

My solution is to use a level-order check . If in certain level, there are several nodes met the BST standard , return the one with biggest size, otherwise go to next level for further check . I use a queue to fulfill this algo, with NULL as level-delimitor .

Node LargestBst ( Tree root )
{
Queue q ;
Node bst ;
Bool start = false ;
int largeSize = 0;

q.Enqueue ( root );
q.Enqueue ( NULL ); /* NULL server as level-delimitor */

while ( ! q.Empty() ) /* Level-Order check */
{
Node temp ;
temp = q.Dequeue() ;

if ( temp == NULL ) /* One level finished , Check out if we have a winner and add NULL
for next level */
{
if ( start == true )
return bst ;
q.Enqueue ( NULL ) ;
temp = q.Dequeue() ;
}

if ( IsBst (temp) ) /* Check out if this node is a BST */
{
start = true ;
if ( Size (temp) > largeSize ) /* Size() is func to calculate BST size */
{
bst = temp ;
largeSize = Size(temp);
}
}
else /* Enqueue its two children for next level check */
{
q.Enqueue( temp->left );
q.Enqueue( temp->right );
}
}

}

int maxbst(struct node *T)
{
int n,l,r;
if(!T)
return 0;
if(T->left==NULL && T->right== NULL)
return 1;
n=CountBst(T);
if(n>0)
return n;
l=maxbst(T->left);
r=maxbst(T->right);
if(l>=r)
return l;
return r;
}
int CountBst(struct node *T)
{
int i;
if(!T)
return 0;
int i=IsBst(T);
if(i!=0)
return CountNodes(T);
return 0;
}

int CountNodes(struct node *T)
{
if(!T)
return 0;
return 1+CountNodes(T->left)+CountNodes(T->right);
}

int IsBst(struct node *T)
{
static struct node *prev;
int p;
if(!T)
return 1;
p=IsBst(T->left);
if(!prev)
prev=T;
else
{
if(prev->info>T->info)
return 0;
pev=T;
}
if(!p)
return 0;
p=IsBst(T->right)
if(!p)
return 0;
return 1;
}

Since it's a binary tree it has at most two nodes ... so all we need to do is figure out number of nodes in left and number of nodes in right, compare and return the bigger one.

We can potentially do inorder traversal on left and right sub trees to get the soln

<pre lang="" line="1" title="CodeMonkey70443" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class BiggestBST {

private static Node rootBST = null;
private static int maxSize = -1;

public static void main(String[] args) {
Node root = buildTree();
findBST(root);
System.out.println("Biggest BST has root --> " + (rootBST == null ? "NULL" : rootBST.getId()));
}

private static Result findBST(Node n) {
if(n == null) {
return new Result(true, 0);
}

boolean isBST = true;
if(
((n.getLeft() != null) && (n.getLeft().getId() > n.getId()))
||
((n.getRight() != null) && (n.getRight().getId() < n.getId()))
) {
isBST = false;
}

int size = 1;

Result resultL = findBST2(n.getLeft());
if(resultL.isBST) {
size += resultL.size;
}

Result resultR = findBST2(n.getRight());
if(resultR.isBST) {
size += resultR.size;
}

isBST = isBST && resultL.isBST && resultR.isBST;
if(isBST) {
bstMap.put(n, size);

if(size > maxSize) {
maxSize = size;
rootBST = n;
}
}

return new Result(isBST, size);
}

private static class Result {
private boolean isBST;
private int size;

Result(boolean isBST, int size) {
this.isBST = isBST;
this.size = size;
}
}

private static Node buildTree() {
Node root = new Node(5);

root.setLeft(new Node(3));
root.setRight(new Node(6));

root.getLeft().setLeft(new Node(1));
root.getLeft().setRight(new Node(4));

root.getRight().setLeft(new Node(9));
root.getRight().setRight(new Node(10));

root.getRight().getLeft().setLeft(new Node(7));

return root;
}
}
</pre><pre title="CodeMonkey70443" input="yes">
</pre>

static int maxBTSize = 0;
int main()
{
int size = 0;
checkIfBST(root, size);
print(maxBTSize);
}

bool checkIfBST(Node* root, int& sizeOfTree)
{
if(root==NULL) return true;

int sizeofLtTree = 0;
bool isLtTreeBST = checkIfBST(root->left, sizeofLtTree);

int sizeofRtTree = 0;
bool isRtTreeBST = checkIfBST(root->right, sizeofRtTree);

if(isLtTreeBST &&
isRtTreeBST &&
root->val > root->left->val &&
root->val < root->left->val
)
{
sizeOfTree = sizeofLtTree + sizeofRtTree + 1;
if(maxBTSize < sizeofTree)
maxBTSize = sizeofTree;
return true;
}
return false;
}

1. Do the inorder traversal of given BT.
2. Then find the longest increasing sequence.
3. Find the sub-tree corresponding to this sequence.

1. Save the count of left most node in the node
2. Save the count of right child of its parent
3. Count of parent = count of left child + count of right child +1
4. Apply these steps recursively (bottom up)
save these values only if the subtree is a BST. For the parent if count of left child and right child is present then they are BST. Now only check the parent and its 2 childs.

1. Save the count of left most node in the node
2. Save the count of right child of its parent
3. Count of parent = count of left child + count of right child +1
4. Apply these steps recursively (bottom up)
save these values only if the subtree is a BST. For the parent if count of left child and right child is present then they are BST. Now only check the parent and its 2 childs.

perform inorder and find longest continous increasing subsequence. longest = whole tree.. novice gave correct solution.

int nodeNumber(node* root)
{
	if (!root) return 0;
	return 1 + nodeNumber(root->lchild) + nodeNumber(root->rchild);
}

int min(root* root)
{
	if (!root)
		return MIN;
	while(root->lchild)
		root = root->lchild;
	return root->element;	
}

int max(root* root)
{
	if (!root)
		return MAX;
	while(root->rchild)
		root = root->rchild;
	return root->element;	
}

bool isBST(node* root)
{
	if(!root) return 1;

	int flag = max(root->child) < root->element && min(root->rchild) > root->element;	

	return flag&&isBST(root->lchild)&&isBST(root->rchild);
}

int maxNodeNumber = MIN;

void maxBST(node* root)
{
	if(isBST(root))
	{
		if(nodeNumber(root) > maxNodeNumber)
			maxNodeNumber = nodeNumber(root);
		return;
	}		
	maxBST(root->lchild);
	maxBST(root->rchild);
	return;
}