// Change the value of node n to Sum(n) for all nodes in the tree, where
// Sum(n) = n.value + Sum(n->left) + Sum(n->right).
//
// For example:
//
//          2                     31
//        /   \                 /   \
//       4     1              23     6
//     /  \     \    ==>     /  \     \
//    7    9     5          7   12     5
//        /                    /
//       3                    3
#include <iostream>

typedef struct Node {
  int data;
  struct Node* left;
  struct Node* right;
} Node;

// ----------------------------------------------------------------------------
// Helper
// ----------------------------------------------------------------------------
void Preorder(Node* n)
{
  if (!n) {
    return;
  }

  std::cout << n->data << std::endl;
  Preorder(n->left);
  Preorder(n->right);
}

void Inorder(Node* n)
{
  if (!n) {
    return;
  }

  Inorder(n->left);
  std::cout << n->data << std::endl;
  Inorder(n->right);
}

void Postorder(Node* n)
{
  if (!n) {
    return;
  }

  Postorder(n->left);
  Postorder(n->right);
  std::cout << n->data << std::endl;
}


// ----------------------------------------------------------------------------
// Standard Postorder Solution
// ----------------------------------------------------------------------------
// void Run(Node* n)
// {
//   if (n->left) {
//     n->data += n->left->data;
//   }

//   if (n->right) {
//     n->data += n->right->data;
//   }
// }

// void SumOfDescendant(Node* n)
// {
//   if (!n) {
//     return;
//   }

//   SumOfDescendant(n->left);
//   SumOfDescendant(n->right);
//   Run(n);
// }

// ----------------------------------------------------------------------------
// One function only solution
// ----------------------------------------------------------------------------
// void SumOfDescendant(Node* n)
// {
//   if (!n) {
//     return;
//   }

//   SumOfDescendant(n->left);
//   SumOfDescendant(n->right);

//   if (n->left) {
//     n->data += n->left->data;
//   }

//   if (n->right) {
//     n->data += n->right->data;
//   }
// }

void SumOfDescendant(Node* n)
{
  if (n->left) {
    SumOfDescendant(n->left);
    n->data += n->left->data;
  }

  if (n->right) {
    SumOfDescendant(n->right);
    n->data += n->right->data;
  }
}

// ----------------------------------------------------------------------------
// Postorder with returned value
// ----------------------------------------------------------------------------
// int SumOfDescendant(Node* n)
// {
//   if (n->left) {
//     n->data += SumOfDescendant(n->left);
//   }

//   if (n->right) {
//     n->data += SumOfDescendant(n->right);
//   }

//   return n->data;
// }

int main()
{
  // Change the value of node n to Sum(n) for all nodes in the tree, where
  // Sum(n) = n.value + Sum(n->left) + Sum(n->right).
  //
  // For example:
  //
  //          2                     31
  //        /   \                 /   \
  //       4     1              23     6
  //     /  \     \    ==>     /  \     \
  //    7    9     5          7   12     5
  //        /                    /
  //       3                    3

  Node a = { 3, nullptr, nullptr };
  Node b = { 5, nullptr, nullptr };
  Node c = { 7, nullptr, nullptr };
  Node d = { 9, &a, nullptr };
  Node e = { 1, nullptr, &b };
  Node f = { 4, &c, &d };
  Node g = { 2, &f, &e };

  SumOfDescendant(&g);

  Preorder(&g);
  Inorder(&g);
  Postorder(&g);

  return 0;
}

// Change the value of node n to Sum(n) for all nodes in the tree, where
// Sum(n) = n.value + Sum(n->left) + Sum(n->right).
//
// For example:
//
//          2                     31
//        /   \                 /   \
//       4     1              23     6
//     /  \     \    ==>     /  \     \
//    7    9     5          7   12     5
//        /                    /
//       3                    3
#include <iostream>
#include <stack>
// #include <utility>

typedef struct Node {
  int data;
  struct Node* left;
  struct Node* right;
} Node;

// ----------------------------------------------------------------------------
// Helper
// ----------------------------------------------------------------------------
void Preorder(Node* n)
{
  if (!n) {
    return;
  }

  std::cout << n->data << std::endl;
  Preorder(n->left);
  Preorder(n->right);
}

void Inorder(Node* n)
{
  if (!n) {
    return;
  }

  Inorder(n->left);
  std::cout << n->data << std::endl;
  Inorder(n->right);
}

void Postorder(Node* n)
{
  if (!n) {
    return;
  }

  Postorder(n->left);
  Postorder(n->right);
  std::cout << n->data << std::endl;
}


// ----------------------------------------------------------------------------
// Standard Postorder Solution
// ----------------------------------------------------------------------------
void Run(Node* n)
{
  if (n->left) {
    n->data += n->left->data;
  }

  if (n->right) {
    n->data += n->right->data;
  }
}

void SumOfDescendant(Node* n)
{
  if (!n) {
    return;
  }

  std::stack<Node*> s;
  std::stack<Node*> output;
  s.push(n);
  while (!s.empty()) {
    n = s.top(); s.pop();
    output.push(n);
    if (n->left) {
      s.push(n->left);
    }
    if (n->right) {
      s.push(n->right);
    }
  }

  while (!output.empty()) {
    n = output.top(); output.pop();
    Run(n);
  }
}

// void SumOfDescendant(Node* n)
// {
//   if (!n) {
//     return;
//   }

//   std::stack<Node*> s;
//   while(true) {
//     if (n) {
//       if(n->right) {
//         s.push(n->right);
//       }
//       s.push(n);
//       n = n->left;
//     } else if(!s.empty()) {
//       n = s.top(); s.pop();
//       if (n->right && !s.empty() && n->right == s.top()) {
//         std::swap(n, s.top());
//       } else {
//         Run(n);
//         n = nullptr; // Force to take the top node in the stack in next round.
//       }
//     } else {
//       break;
//     }
//   }
// }


int main()
{
  // Change the value of node n to Sum(n) for all nodes in the tree, where
  // Sum(n) = n.value + Sum(n->left) + Sum(n->right).
  //
  // For example:
  //
  //          2                     31
  //        /   \                 /   \
  //       4     1              23     6
  //     /  \     \    ==>     /  \     \
  //    7    9     5          7   12     5
  //        /                    /
  //       3                    3

  Node a = { 3, nullptr, nullptr };
  Node b = { 5, nullptr, nullptr };
  Node c = { 7, nullptr, nullptr };
  Node d = { 9, &a, nullptr };
  Node e = { 1, nullptr, &b };
  Node f = { 4, &c, &d };
  Node g = { 2, &f, &e };

  SumOfDescendant(&g);

  Preorder(&g);
  Inorder(&g);
  Postorder(&g);

  return 0;
}