A Developer's Diary

Mar 25, 2012

Vertical Sum of a Binary Tree

The binary tree above can be represented as the following to calculate the vertical sum of the nodes

class BinaryTreeVerticalSumPrinter
{
  public:
    BinaryTreeVerticalSumPrinter(){}
   ~BinaryTreeVerticalSumPrinter(){}
    
    void verticalSum(BinarySearchTree &tree)
    {
      std::map<int, int> vsum;
      verticalSum(tree.root, 0, vsum);
      printSum(vsum);
    }

  private:
    void verticalSum(BinaryTreeNode *node, int idx, std::map<int, int> &vsum)
    {
      if(node)
      {
        vsum[idx] = vsum[idx] + node->data;
        verticalSum(node->left, idx - 1, vsum);
        verticalSum(node->right, idx + 1, vsum);
      }
    }

    void printSum(std::map<int, int> &vsum)
    {
      std::map<int, int>::iterator pos;
      std::cout << std::endl;
      for(pos = vsum.begin(); pos != vsum.end(); ++pos)
      {
        std::cout << "Key: " << pos->first << " Value: " << pos->second << std::endl;
      }
    }
};

No comments :

Post a Comment