Largest Continuous/Non-Continuous BST in a Binary Tree
Given a binary tree, find the largest continuous/non-continuous Binary Search Tree (BST), where largest means BST with largest number of nodes in it. Note, in the final BST, the relationship among the nodes must be preserved i.e if, in the given binary tree, node A is left descendant of a node B then in the BST, A must be left descendant of B(if both are part of final BST). Similarly for the right descendants. 

Example:

Input:

                    10
                   /  \
                 50    150
                /  \     \
               5    75    20
              / \         / \
             3   7       12 35

Largest BST:

                     10
                   /   \
                  5     20
                 / \    / \
                3   7  12 35

I hope, you got the point what I am trying to make here regarding continuous/non-continuous BST.

What I did so far?

    Greedy Approach: At every node N, try to finding out MaxBST.  
                          --
                         |  MaxBST(R->left),
            MaxBST(R) = <   MaxBST(R->right),
                         |  MaxBST(R->left) + MaxBST(R->right) + 1, if left and right BSTs can be combined.
                          -- 

    Conclusion: May not give optimal solution in each case. 
                Consider the root node i.e 10 in the above example, MaxBST(left) = 5
                (BST rooted at 50) and MaxBST(right) = 3 (BST rooted at 20), but as 
                we have seen, we can have LCNC BST of size 7 rooted at 10.
 
.

    Dynamic Programming: Do an inorder traversal of the given tree and store that in 
                         an array. Now apply the [Longest increasing subsequence][1] 
                         algo to get the size of the LCNC BST.

    Conclusion: May not give correct solution in each case as an increasing 
                subsequence may not corresponds to a valid BST. For example - 
                Consider the tree in the above example. its inorder traversal gives
             
                3 5 7 50 75 10 150 12 20 35
       
                One of the increasing subsequences is : 3 5 7 50 75 150 but it 
                doesn't correspond to a valid BST.
 
.

    Dynamic Programming: Another approach that is coming to my mind is that, for 
                         every node k, calculate the Max Size BST rooted at k. Once
                         we got this table, we can simply traverse it to find the
                         solution. I am facing problem in finding out the recurrence
                         relationship among the subproblem i.e given
                         Max_BST_Rooted_Here for all left and right descendants, 
                         how to find out the Max_BST_Rooted_Here for the current 
                         node.

Is it possible to do it using Dynamic Programming?

  [1]: http://en.wikipedia.org/wiki/Longest_increasing_subsequence
Largest Continuous/Non-Continuous BST in a Binary Tree
===

Given a binary tree, find the largest continuous/non-continuous Binary Search Tree (BST), where largest means BST with largest number of nodes in it. Note, in the final BST, the relationship among the nodes must be preserved i.e if, in the given binary tree, node A is left descendant of a node B then in the BST, A must be left descendant of B(if both are part of final BST). Similarly for the right descendants. 

Example:

Input:

                    10
                   /  \
                 50    150
                /  \     \
               5    75    20
              / \         / \
             3   7       12 35

Largest BST:

                     10
                   /   \
                  5     20
                 / \    / \
                3   7  12 35

I hope, you got the point what I am trying to make here regarding continuous/non-continuous BST.

What I did so far?

    Greedy Approach: At every node N, try to finding out MaxBST.  
                          --
                         |  MaxBST(R->left),
            MaxBST(R) = <   MaxBST(R->right),
                         |  MaxBST(R->left) + MaxBST(R->right) + 1, if left and right BSTs can be combined.
                          -- 

    Conclusion: May not give optimal solution in each case. 
                Consider the root node i.e 10 in the above example, MaxBST(left) = 5
                (BST rooted at 50) and MaxBST(right) = 3 (BST rooted at 20), but as 
                we have seen, we can have LCNC BST of size 7 rooted at 10.
 
.

    Dynamic Programming: Do an inorder traversal of the given tree and store that in 
                         an array. Now apply the [Longest increasing subsequence][1] 
                         algo to get the size of the LCNC BST.

    Conclusion: May not give correct solution in each case as an increasing 
                subsequence may not corresponds to a valid BST. For example - 
                Consider the tree in the above example. its inorder traversal gives
             
                3 5 7 50 75 10 150 12 20 35
       
                One of the increasing subsequences is : 3 5 7 50 75 150 but it 
                doesn't correspond to a valid BST.
 
.

    Dynamic Programming: Another approach that is coming to my mind is that, for 
                         every node k, calculate the Max Size BST rooted at k. Once
                         we got this table, we can simply traverse it to find the
                         solution. I am facing problem in finding out the recurrence
                         relationship among the subproblem i.e given
                         Max_BST_Rooted_Here for all left and right descendants, 
                         how to find out the Max_BST_Rooted_Here for the current 
                         node.

Is it possible to do it using Dynamic Programming?

  [1]: http://en.wikipedia.org/wiki/Longest_increasing_subsequence