Comment on page
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;
}
Last modified 4yr ago