Root to leaf paths having equal lengths in a Binary Tree | Java 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 code
import java . util . HashMap ; import java . util . Map ; class GFG { static class Node { int data ; Node left , right ; } ; static Node newnode ( int data ) { Node node = new Node ( ) ; node . data = data ; node . left = node . right = null ; return ( node ) ; } static void pathCountUtil ( Node node , HashMap < Integer , Integer > m , int path_len ) { if ( node == null ) return ; if ( node . left == null && node . right == null ) { if ( ! m . containsKey ( path_len ) ) m . put ( path_len , 0 ) ; m . put ( path_len , m . get ( path_len ) + 1 ) ; return ; } pathCountUtil ( node . left , m , path_len + 1 ) ; pathCountUtil ( node . right , m , path_len + 1 ) ; } static void pathCounts ( Node root ) { HashMap < Integer , Integer > m = new HashMap < > ( ) ; pathCountUtil ( root , m , 1 ) ; for ( Map . Entry < Integer , Integer > entry : m . entrySet ( ) ) { System . out . printf ( "%d paths have length %dNEW_LINE", entry . getValue ( ) , entry . getKey ( ) ) ; } } public static void main ( String [ ] args ) { 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 ) ; } }