CareerCup

//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";
   }
}

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.

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.

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

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

}

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

}

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;

}

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

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

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

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]

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 !

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.

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.

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
1. start with current

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.

Comments/working code welcome :)

Example graph did not go through well.

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

{ }

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

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

Please comment on my solution...

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?

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

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

@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.

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

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());
        t1.add(3);
        Assert.assertEquals(Integer.valueOf(2), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
        t1.add(7);
        Assert.assertEquals(Integer.valueOf(3), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
        t1.add(6);
        Assert.assertEquals(Integer.valueOf(4), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
        t1.add(9);
        Assert.assertEquals(Integer.valueOf(5), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
        t1.add(1);
        Assert.assertEquals(Integer.valueOf(6), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
        t1.add(4);
        Assert.assertEquals(Integer.valueOf(7), TreesAndGraphs.getMaxNodesBst(t1.getRoot()).getMaxDepth());
        t1.add(11);
        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.

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

use dynamic programming...