Binary Tree (DFS application)

Problem Link : Number of Good Leaf Nodes Pairs

Description and Intuition :

Given a root of the binary tree , we need to determine number of pair of leaf nodes that are at distance apart.

Logically this problem seems to be very insightful as we just need to determine a leaf node and find all nodes that are leaf node which are at a distance “d” apart from the current leaf node. But there is a problem in this, for every leaf node to find every other leaf node we need to traverse the tree many times and is time consuming, asymtotically O(n*n) TC.
In order to optimise this we need to think of such solution where we do not need to traverse all nodes every time when we want to find distance between two leaf nodes. One way to solve this problem can be try traversing the tree from bottom to top. For every node while traversing, we return {} (empty array) for any root==NULL and return {1} for any leaf node. This helps us find the height of every leaf node from current node while we are traversing from bottom to top in the binary tree. Then simply, we merge both the left and right arrays for any node while traversing from bottom to top and increment the height by 1 and return the merged array. Our ans counter increments if the each left height when added up to very right height for any leaf node at current node equals to the target distance.

This approach optimises the previous brute force as for every node this time we traverse only leaf nodes and we get the following complexities :

Time Complexity : O(n * #leafNodes * #leafNodes)

Space Complexity : O(n)