## Monday, December 19, 2016

### 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;`
`}`