Another rough and ready algorithm. Finding the greatest subtree in a binary tree…<\/p>\n
Things to remember, values in the tree can be negative so it’s not just the root (sigh).<\/p>\n
This implementation is very inefficient. Caching sum in the node makes the efficiency reasonable I believe. But the problem is essentially recursive? Should do some googling to see if there is a better solution.<\/p>\n
\r\n#include <iostream>\r\n\r\nusing namespace std;\r\n\r\nclass Node {\r\n\r\npublic:\r\n\r\n Node () : left(NULL), right(NULL) {}\r\n\r\n int value;\r\n int sum;\r\n\r\n Node *left;\r\n Node *right;\r\n\r\n int getsum() {\r\n sum = 0;\r\n if((left == NULL) && (right == NULL)) return value;\r\n\r\n if(left != NULL) sum += left->getsum();\r\n if(right != NULL) sum += right->getsum();\r\n sum += value;\r\n\r\n return sum;\r\n }\r\n};\r\n\r\n\r\nNode *greatestsubtree(Node *current,Node *max) {\r\n\r\n if(current == NULL) return max;\r\n\r\n int mval = current->getsum();\r\n\r\n if(mval > max->getsum()) max = current;\r\n\r\n Node *l = greatestsubtree(current->left,max);\r\n Node *r = greatestsubtree(current->right,max);\r\n if(l->getsum() > max->getsum()) max = l;\r\n if(r->getsum() > max->getsum()) max = r;\r\n\r\n return max;\r\n}\r\n\r\nint main() {\r\n\r\n Node *root = new Node();\r\n root->left = new Node();\r\n root->right = new Node();\r\n root->value = 10;\r\n\r\n root->left->value = -10;\r\n root->right->value = 5;\r\n\r\n root->left->left = new Node();\r\n root->left->left->value = 100;\r\n root->left->right = new Node();\r\n root->left->right->value = 0;\r\n\r\n root->right->left = new Node();\r\n root->right->left->value = -8;\r\n\r\n cout << root << endl;\r\n cout << greatestsubtree(root,root)->getsum();\r\n}\r\n<\/pre>\nVersion with caching…<\/p>\n
\r\n\r\n#include <iostream>\r\n\r\nusing namespace std;\r\n\r\nclass Node {\r\n\r\npublic:\r\n\r\n Node () : left(NULL), right(NULL),sumcache(false) {}\r\n\r\n int value;\r\n int sum;\r\n bool sumcache;\r\n \r\n Node *left;\r\n Node *right;\r\n \r\n int getsum() {\r\n\r\n if(sumcache) return sum;\r\n\r\n sum = 0;\r\n if((left == NULL) && (right == NULL)) return value;\r\n \r\n if(left != NULL) sum += left->getsum();\r\n if(right != NULL) sum += right->getsum();\r\n sum += value;\r\n \r\n sumcache = true;\r\n return sum;\r\n }\r\n};\r\n\r\n\r\nNode *greatestsubtree(Node *current,Node *max) {\r\n\r\n if(current == NULL) return max;\r\n\r\n int mval = current->getsum();\r\n \r\n if(mval > max->getsum()) max = current;\r\n\r\n Node *l = greatestsubtree(current->left,max);\r\n Node *r = greatestsubtree(current->right,max);\r\n if(l->getsum() > max->getsum()) max = l;\r\n if(r->getsum() > max->getsum()) max = r;\r\n\r\n return max;\r\n}\r\n\r\nint main() {\r\n\r\n Node *root = new Node();\r\n root->left = new Node();\r\n root->right = new Node();\r\n root->value = 10;\r\n\r\n root->left->value = -10;\r\n root->right->value = 5;\r\n\r\n root->left->left = new Node();\r\n root->left->left->value = 100;\r\n root->left->right = new Node();\r\n root->left->right->value = 0;\r\n\r\n root->right->left = new Node();\r\n root->right->left->value = -8;\r\n\r\n cout << root << endl;\r\n cout << greatestsubtree(root,root)->getsum();\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"Another rough and ready algorithm. Finding the greatest subtree in a binary tree… Things to remember, values in the tree can be negative so it’s not just the root (sigh). This implementation is very inefficient. Caching sum in the node makes the efficiency reasonable I believe. But the problem is essentially recursive? Should do some […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-848","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p1RRoU-dG","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/848","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/comments?post=848"}],"version-history":[{"count":3,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/848\/revisions"}],"predecessor-version":[{"id":851,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/848\/revisions\/851"}],"wp:attachment":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/media?parent=848"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/categories?post=848"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/tags?post=848"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}