largestBST

#include <iostream>
#include <stdio.h>

/*
               ___________________15___________________
              /                                        \
  ___________10___________                             20
 /                        \
 5                   _____7____
                    /          \
                  __2__       __5
                 /     \     /
                 0      8    3
*/

/*
         _________11_________
        /                    \
       12      ______________15______________
              /                              \
  ___________10___________                   20
 /                        \
 5                   _____7____
                    /          \
                  __2__       __5
                 /     \     /
                 0      8    3
*/

class BinaryTree
{
    public:
    int data;
    // Store current tree size to avoid computing it over and over again...
    int size;
    BinaryTree *left, *right;

    BinaryTree(int d, BinaryTree *l=NULL, BinaryTree *r=NULL){
        data = d;
        left = l;
        right = r;
        updateSize();
    }

    ~BinaryTree(){
        if (left != NULL) delete(left);
        if (right != NULL) delete(right);
    }

    void print(){
        if (left || right){
            printf("(%i, ", data);
            if (left)  left->print(); else printf("NULL");
            printf(", ");
            if (right) right->print(); else printf("NULL");
            printf(")");
        } else printf("(%i)", data);
    }

    void updateSize(){
        size = 1;
        if (left != NULL){
            size += left->size;
        }
        if (right != NULL){
            size += right->size;
        }
    }
} ;

#define B new BinaryTree

// Limit lower bound
// O(log n)
BinaryTree *boundMin(BinaryTree *t, int min){
    if ((t == NULL) || (t->data < min)) return NULL;

    t->left = boundMin(t->left, min);
    t->updateSize();

    return t;
}

// Limit upper bound
// O(log n)
BinaryTree *boundMax(BinaryTree *t, int max){
    if ((t == NULL) || (t->data > max)) return NULL;

    t->right = boundMax(t->right, max);
    t->updateSize();

    return t;
}

// Find the largest BST : bottom up approach. Start down, and when moving up,
// recreate a tree from which we can cut off the branches that don't
// respect the BST...
// n nodes visisted, each step is 2 * O(log n) => O(n log n)
BinaryTree *findLargestBST(BinaryTree *p, int &maxNodes, BinaryTree *&largestBST) {
  if (!p) return NULL;

  // Bottom up approach... Check out the children first...
  BinaryTree *left = findLargestBST(p->left, maxNodes, largestBST);
  BinaryTree *right = findLargestBST(p->right, maxNodes, largestBST);

  // Limit the max value on the left side...
  left = boundMax(left, p->data);

  // Limit the min value on the right side
  right = boundMin(right, p->data);

  BinaryTree *t = new BinaryTree(p->data, left, right);

  // New tree is actually better than the other ones !
  if(t->size > maxNodes){
      maxNodes = t->size;
      largestBST = p;   // Store root node from ORIGINAL tree
  }

  return t;
}

// Turn a tree into a BST by cutting off the nodes that
// don't respect the BST constraints...
// Maximum n nodes => O(n)
BinaryTree *tree2BST(BinaryTree *t, int min, int max){
    // End case
    if (t == NULL) return NULL;

    // No node
    if ((t->data < min) || (t->data > max)) return NULL;

    t->left = tree2BST(t->left, min, t->data);
    t->right = tree2BST(t->right, t->data, max);
    return t;
}

// Fint the largestBST's root node, then create the BST from it
// O(n log n) + O(n) => O(n log n)
BinaryTree* findLargestBST(BinaryTree *root) {
  BinaryTree *largestBST = NULL;
  int maxNodes = INT_MIN;

  // Find root...
  findLargestBST(root, maxNodes, largestBST);
  printf("Size : %i\n", maxNodes);

  // Create BST from the largestBST's root
  largestBST = tree2BST(largestBST, INT_MIN, INT_MAX);
  largestBST->print();
  printf("\n");

  return largestBST;
}

int main()
{
    //BinaryTree *b = B( 15, B(10, B(5), B(7, B(2, B(0), B(8)), B(5, B(3), NULL))), B(20));
    BinaryTree *b = B(11, B(12), B( 15, B(10, B(5), B(7, B(2, B(0), B(8)), B(5, B(3), NULL))), B(20)));

    b->print();
    printf("\n");
    findLargestBST(b);

    return 0;
}