> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/interview-practice-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/trees-and-graphs/largest-subtree.md).

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

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