Count pairs of leaf nodes in a Binary Tree which are at most K distance apart | C # implementation of the above approach ; Structure of a Node ; Constructor of the class ; Stores the count of required pairs ; Function to perform dfs to find pair of leaf nodes at most K distance apart ; Return empty array if node is null ; If node is a leaf node and return res ; Traverse to the left ; Traverse to the right ; Update the distance between left and right leaf node ; Count all pair of leaf nodes which are at most K distance apart ; Return res to parent node ; Driver Code ; 1 / \ 2 3 / 4 ; Given distance K ; Function Call
using System ; class Node { public int data ; public Node left , right ; public Node ( int item ) { data = item ; left = right = null ; } } class GFG { Node root ; static int result ; static int [ ] dfs ( Node root , int distance ) { int [ ] res ; if ( root == null ) return new int [ distance + 1 ] ; if ( root . left == null && root . right == null ) { res = new int [ distance + 1 ] ; res [ 1 ] ++ ; return res ; } int [ ] left = dfs ( root . left , distance ) ; int [ ] right = dfs ( root . right , distance ) ; res = new int [ distance + 1 ] ; for ( int i = res . Length - 2 ; i >= 1 ; i -- ) { res [ i + 1 ] = left [ i ] + right [ i ] ; } for ( int l = 1 ; l < left . Length ; l ++ ) { for ( int r = 0 ; r < right . Length ; r ++ ) { if ( l + r <= distance ) { result += left [ l ] * right [ r ] ; } } } return res ; } public static void Main ( String [ ] args ) { GFG tree = new GFG ( ) ; tree . root = new Node ( 1 ) ; tree . root . left = new Node ( 2 ) ; tree . root . right = new Node ( 3 ) ; tree . root . left . left = new Node ( 4 ) ; result = 0 ; int K = 3 ; dfs ( tree . root , K ) ; Console . WriteLine ( result ) ; } }