Count pairs of leaf nodes in a Binary Tree which are at most K distance apart | C ++ 14 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; Node * left , * right ; Node ( int item ) { data = item ; left = right = NULL ; } } ; int result = 0 ; vector < int > dfs ( Node * root , int distance ) { if ( root == NULL ) { vector < int > res ( distance + 1 , 0 ) ; return res ; } if ( root -> left == NULL && root -> right == NULL ) { vector < int > res ( distance + 1 , 0 ) ; res [ 1 ] ++ ; return res ; } vector < int > left = dfs ( root -> left , distance ) ; vector < int > right = dfs ( root -> right , distance ) ; vector < int > res ( distance + 1 , 0 ) ; for ( int i = res . size ( ) - 2 ; i >= 1 ; i -- ) res [ i + 1 ] = left [ i ] + right [ i ] ; for ( int l = 1 ; l < left . size ( ) ; l ++ ) { for ( int r = 0 ; r < right . size ( ) ; r ++ ) { if ( l + r <= distance ) { result += left [ l ] * right [ r ] ; } } } return res ; } int main ( ) { Node * root = new Node ( 1 ) ; root -> left = new Node ( 2 ) ; root -> right = new Node ( 3 ) ; root -> left -> left = new Node ( 4 ) ; int K = 3 ; dfs ( root , K ) ; cout << result ; }