# Root to leaf paths having equal lengths in a Binary Tree

Given a binary tree, print the number of root to leaf paths having equal lengths.

Examples:

```Input : Root of below tree
10
/
8      2
/      /
3     5  2    4
Output : 4 paths are of length 3.

Input : Root of below tree
10
/
8      2
/      /
3    5  2    4
/
9                 1
Output : 2 paths are of length 3
2 paths are of length 4
```

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.

## C++

 `// C++ program to count root to leaf paths of different ` `// lengths. ` `#include ` `using` `namespace` `std; ` ` `  `/* A binary tree node */` `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node* left, *right; ` `}; ` ` `  `/* utility that allocates a new node with the ` `   ``given data and NULL left and right pointers. */` `struct` `Node* newnode(``int` `data) ` `{ ` `    ``struct` `Node* node = ``new` `Node; ` `    ``node->data = data; ` `    ``node->left = node->right  = NULL; ` `    ``return` `(node); ` `} ` ` `  `// 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; ` `} ` ` `  `// Driver program to run the case ` `int` `main() ` `{ ` `    ``struct` `Node *root = newnode(8); ` `    ``root->left    = newnode(5); ` `    ``root->right   = newnode(4); ` `    ``root->left->left = newnode(9); ` `    ``root->left->right = newnode(7); ` `    ``root->right->right = newnode(11); ` `    ``root->right->right->left = newnode(3); ` `    ``pathCounts(root); ` `    ``return` `0; ` `} `

## Python3

 `# Python3 program to count root to leaf  ` `# paths of different lengths. ` `     `  `# Binary Tree Node  ` `""" utility that allocates a newNode  ` `with the given key """` `class` `newnode:  ` ` `  `    ``# Construct to create a newNode  ` `    ``def` `__init__(``self``, key):  ` `        ``self``.key ``=` `key ` `        ``self``.left ``=` `None` `        ``self``.right ``=` `None` `         `  `# Function to store counts of different  ` `# root to leaf path lengths in hash map m.  ` `def` `pathCountUtil(node, m,path_len) : ` ` `  `    ``# Base condition  ` `    ``if` `(node ``=``=` `None``) : ` `        ``return` ` `  `    ``# If leaf node reached, increment count of  ` `    ``# path length of this root to leaf path.  ` `    ``if` `(node.left ``=``=` `None` `and` `node.right ``=``=` `None``):    ` `        ``if` `path_len[``0``] ``not` `in` `m: ` `            ``m[path_len[``0``]] ``=` `0` `        ``m[path_len[``0``]] ``+``=` `1` `        ``return` ` `  `    ``# Recursively call for left and right  ` `    ``# subtrees with path lengths more than 1. ` `    ``pathCountUtil(node.left, m, [path_len[``0``] ``+` `1``]) ` `    ``pathCountUtil(node.right, m, [path_len[``0``] ``+` `1``])  ` ` `  `# A wrapper over pathCountUtil()  ` `def` `pathCounts(root) : ` ` `  `    ``# create an empty hash table  ` `    ``m ``=` `{} ` `    ``path_len ``=` `[``1``] ` `     `  `    ``# Recursively check in left and right subtrees.  ` `    ``pathCountUtil(root, m, path_len)  ` ` `  `    ``# Print all path lenghts and their counts.  ` `    ``for` `itr ``in` `sorted``(m, reverse ``=` `True``): ` `        ``print``(m[itr], ``" paths have length "``, itr)  ` ` `  `# Driver Code  ` `if` `__name__ ``=``=` `'__main__'``: ` ` `  `    ``root ``=` `newnode(``8``)  ` `    ``root.left ``=` `newnode(``5``)  ` `    ``root.right ``=` `newnode(``4``)  ` `    ``root.left.left ``=` `newnode(``9``)  ` `    ``root.left.right ``=` `newnode(``7``)  ` `    ``root.right.right ``=` `newnode(``11``)  ` `    ``root.right.right.left ``=` `newnode(``3``)  ` `    ``pathCounts(root) ` ` `  `# This code is contributed by ` `# Shubham Singh(SHUBHAMSINGH10) `

Output:

```1 paths have length 4
2 paths have length 3
```

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

## tags:

Hash Tree Hash Tree

code

load comments