Root to leaf paths having equal lengths in a Binary Tree | C ++ program to count root to leaf paths of different lengths . ; A binary tree node ; utility that allocates a new node with the given data and NULL left and right pointers . ; Function to store counts of different root to leaf path lengths in hash map m . ; Base condition ; If leaf node reached , increment count of path length of this root to leaf path . ; Recursively call for left and right subtrees with path lengths more than 1. ; A wrapper over pathCountUtil ( ) ; create an empty hash table ; Recursively check in left and right subtrees . ; Print all path lenghts and their counts . ; Driver program to run the case
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * left , * right ; } ; struct Node * newnode ( int data ) { struct Node * node = new Node ; node -> data = data ; node -> left = node -> right = NULL ; return ( node ) ; } void pathCountUtil ( Node * node , unordered_map < int , int > & m , int path_len ) { if ( node == NULL ) return ; if ( node -> left == NULL && node -> right == NULL ) { m [ path_len ] ++ ; return ; } pathCountUtil ( node -> left , m , path_len + 1 ) ; pathCountUtil ( node -> right , m , path_len + 1 ) ; } void pathCounts ( Node * root ) { unordered_map < int , int > m ; pathCountUtil ( root , m , 1 ) ; for ( auto itr = m . begin ( ) ; itr != m . end ( ) ; itr ++ ) cout << itr -> second << " ▁ paths ▁ have ▁ length ▁ " << itr -> first << endl ; } 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 ; }