Count pairs of leaf nodes in a Binary Tree which are at most K distance apart | 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 ; 1 / \ 2 3 / 4 ; Given distance K ; Function Call
class Node { constructor ( item ) { this . left = null ; this . right = null ; this . data = item ; } } let root ; class GFG { } let result ; function dfs ( root , distance ) { if ( root == null ) { let arr = new Array ( distance + 1 ) ; arr . fill ( 0 ) ; return arr ; } if ( root . left == null && root . right == null ) { let res = new Array ( distance + 1 ) ; res . fill ( 0 ) ; res [ 1 ] ++ ; return res ; } let left = dfs ( root . left , distance ) ; let right = dfs ( root . right , distance ) ; let res = new Array ( distance + 1 ) ; res . fill ( 0 ) ; for ( let i = res . length - 2 ; i >= 1 ; i -- ) { res [ i + 1 ] = left [ i ] + right [ i ] ; } for ( let l = 1 ; l < left . length ; l ++ ) { for ( let r = 0 ; r < right . length ; r ++ ) { if ( l + r <= distance ) { result += left [ l ] * right [ r ] ; } } } return res ; } let 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 ; let K = 3 ; dfs ( tree . root , K ) ; document . write ( result ) ;