Largest Subtree

Given a Btree, return the count of the largest subtree in linear time.

The Idea: Overwrite the tree with an accumulation tree. This particular accumulation tree builds bottom up to represent the number of nodes within its particular subtree. This creates a dynamic setting in which we can traverse through the find the particular node with the greatest uniform weight.

void buildAccumulationTree(TreeNode* root) {
    if (root) {
        buildAccumulationTree(root->left);
        buildAccumulationTree(root->right);
        root->val = 1;
        if (!root->left && !root->right) {
            root->val = 1;
        }
        else {
            if (root->left) 
                root->val += root->left->val;

            if (root->right) 
                root->val += root->right->val;
        }
    }
}

void FindMaxElm(TreeNode *root, int &cur_max) {
    if (root) {
        FindMaxElm(root->left, cur_max);
        cur_max = max(cur_max, root->val);
        FindMaxElm(root->right, cur_max);
    }
}

int largestBSTSubtree(TreeNode* root) {
    buildAccumulationTree(root);
    int cur_max = 0;
    // root is not a subtree, so ignore it
    if (root) root->val = 1;
    FindMaxElm(root, cur_max);
    return cur_max;
}