fork download
copy 
  1. #include <iostream>
  2. #include<queue>
  3.  
  4. using namespace std;
  5.  
  6. class TreeNode {
  7. public:
  8.     int val;
  9.     TreeNode *left;
  10.     TreeNode *right;
  11.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  12. };
  13.  
  14. class BinaryTree {
  15. public:
  16.  
  17.     TreeNode* root;
  18.     BinaryTree(TreeNode* r) : root(r) {}
  19.  
  20.     ~BinaryTree() {
  21.         clear(root);
  22.     }
  23.  
  24.     void printTree() {
  25.         if (!root) {
  26.             cout << "Tree is empty";
  27.             return;
  28.         }
  29.  
  30.         printTree(root, 0);
  31.     }
  32.     void printTree(TreeNode* root, int level) {
  33.         if (root == nullptr) {
  34.             return;
  35.         }
  36.  
  37.         printTree(root->right, level + 1);
  38.  
  39.         for (int i = 0; i < level; i++) {
  40.             cout << "    ";
  41.         }
  42.  
  43.         cout << root->val << "\n";
  44.  
  45.         printTree(root->left, level + 1);
  46.     }
  47.  
  48.     int calcMaxSubTreeSum() {
  49.     if (root == NULL) return 0;
  50.     int ans = -10000;
  51.     MaxSubTree(root, ans);
  52.     return ans;
  53.     }
  54.     TreeNode* subroot;
  55.     // Recursive function to calculate the sum of nodes
  56.     int MaxSubTree(TreeNode* root, int& ans) {
  57.     if (root == NULL) return 0;
  58.     int currSum = root->val + MaxSubTree(root->left, ans) + MaxSubTree(root->right, ans);
  59.     if (ans<currSum) subroot = root;
  60.     ans = max(ans, currSum);
  61.     return currSum;
  62.     }
  63.  
  64.     void printMaxSubTree() {
  65.         if (!root) {
  66.             cout << "Tree is empty";
  67.             return;
  68.         }
  69.  
  70.         printTree(subroot, 0);
  71.     }
  72.  
  73.     void insert(int val) {
  74.         if (!root) {
  75.             root = new TreeNode(val);
  76.             return;
  77.         }
  78.         TreeNode* current = root;
  79.         TreeNode* parent = nullptr;
  80.         while (current) {
  81.             parent = current;
  82.             if (val < current->val)
  83.                 current = current->left;
  84.             else
  85.                 current = current->right;
  86.         }
  87.         if (val < parent->val)
  88.             parent->left = new TreeNode(val);
  89.         else
  90.             parent->right = new TreeNode(val);
  91.     }
  92.  
  93. private:
  94.     void clear(TreeNode* node) {
  95.         if (node) {
  96.             clear(node->left);
  97.             clear(node->right);
  98.             delete node;
  99.         }
  100.     }
  101. };
  102.  
  103. int main() {
  104.     BinaryTree tree(nullptr);
  105.     tree.insert(-15);
  106.     tree.insert(-18);
  107.     tree.insert(-10);
  108.     tree.insert(-20);
  109.     tree.insert(-16);
  110.     tree.insert(-21);
  111.     tree.insert(-19);
  112.     tree.insert(-17);
  113.     tree.insert(-12);
  114.     tree.insert(-5);
  115.     tree.insert(-7);
  116.     tree.insert(2);
  117.     tree.insert(0);
  118.     tree.insert(7);
  119.     tree.insert(-2);
  120.     tree.insert(1);
  121.     tree.insert(4);
  122.     tree.insert(8);
  123.     tree.printTree();
  124.  
  125.     cout << "Maximum sum subtree has sum of elemnets: " << tree.calcMaxSubTreeSum() << endl;
  126.     tree.printMaxSubTree();
  127.  
  128.     return 0;
  129. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
                    8
                7
                    4
            2
                    1
                0
                    -2
        -5
            -7
    -10
        -12
-15
        -16
            -17
    -18
            -19
        -20
            -21
Maximum sum subtree has sum of elemnets: 20
        8
    7
        4
2
        1
    0
        -2
https://ideone.com/veO95k
language:
C++ 4.3.2 (gcc-4.3.2)
created:
15 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!