Root to leaf paths having equal lengths in a Binary Tree

http://www.geeksforgeeks.org/root-leaf-paths-equal-lengths-binary-tree

The idea is to traverse the tree and keep track of path length. Whenever we reach a leaf node, we increment path length count in a hash map.
Once we have traverse the tree, hash map has counts of distinct path lengths. Finally we print contents of hash map.

// Function to store counts of different root to leaf

// path lengths in hash map m.

void pathCountUtil(Node *node, unordered_map<int, int> &m,

                                             int path_len)

{

    // Base condition

    if (node == NULL)

        return;

 

    // If leaf node reached, increment count of path

    // length of this root to leaf path.

    if (node->left == NULL && node->right == NULL)

    {

         m[path_len]++;

         return;

    }

 

    // Recursively call for left and right subtrees with

    // path lengths more than 1.

    pathCountUtil(node->left, m, path_len+1);

    pathCountUtil(node->right, m, path_len+1);

}

 

// A wrapper over pathCountUtil()

void pathCounts(Node *root)

{

   // create an empty hash table

   unordered_map<int, int> m;

 

   // Recursively check in left and right subtrees.

   pathCountUtil(root, m, 1);

 

   // Print all path lenghts and their counts.

   for (auto itr=m.begin(); itr != m.end(); itr++)

      cout << itr->second << " paths have length "

           << itr->first << endl;

}