Leaf Pairs Less Than Target Distance Away - Google Top Interview Questions

                        Solution in C++ :

vector<int> tra(Tree* root, int k, int& ans) {
    if (!root) return {};
    if (root->left == root->right) {
        return {0, 1};
    }
    vector<int> left = tra(root->left, k, ans);
    vector<int> right = tra(root->right, k, ans);
    for (int i = 1; i < left.size(); i++) {
        for (int j = 1; j < right.size(); j++) {
            if (i + j <= k) {
                ans += left[i] * right[j];
            }
        }
    }
    int final_len = max((int)left.size(), (int)right.size()) + 1;
    vector<int> ret(final_len + 1, 0);
    for (int i = 2; i < final_len; i++) {
        if (left.size() >= i) ret[i] += left[i - 1];
        if (right.size() >= i) ret[i] += right[i - 1];
    }
    return ret;
}
int solve(Tree* root, int target) {
    int ans = 0;
    tra(root, target, ans);
    return ans;
}
                    

                        Solution in Java :

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    HashMap<Tree, ArrayList<Tree>> graph;
    ArrayList<Tree> leaves;

    public boolean is_leaf(Tree root) {
        return root.left == null && root.right == null;
    }

    public int solve(Tree root, int target) {
        graph = new HashMap();
        leaves = new ArrayList();
        fill(root);

        HashSet<Pair<Tree, Tree>> hs = new HashSet();

        for (Tree leaf : leaves) {
            int dist = 0;
            LinkedList<Tree> q = new LinkedList();
            HashSet<Tree> visited = new HashSet();
            visited.add(leaf);
            q.add(leaf);

            while (q.size() > 0 && dist < target) {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    Tree cur = q.removeFirst();
                    visited.add(cur);

                    for (Tree neighbor : graph.get(cur)) {
                        if (visited.contains(neighbor))
                            continue;
                        if (is_leaf(neighbor))
                            hs.add(new Pair(neighbor, leaf));
                        q.addLast(neighbor);
                        visited.add(neighbor);
                    }
                }
                dist++;
            }
        }
        return hs.size() / 2;
    }

    public void fill(Tree root) {
        if (root == null)
            return;

        if (root.left == null && root.right == null) {
            leaves.add(root);
        }

        graph.putIfAbsent(root, new ArrayList());

        if (root.left != null) {
            graph.get(root).add(root.left);
            graph.putIfAbsent(root.left, new ArrayList());
            graph.get(root.left).add(root);
        }

        if (root.right != null) {
            graph.get(root).add(root.right);
            graph.putIfAbsent(root.right, new ArrayList());
            graph.get(root.right).add(root);
        }

        fill(root.left);
        fill(root.right);
    }
}
                    

                        Solution in Python : 
                            
# class Tree:
#     def __init__(self, val, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def solve(self, root, target):
        res = 0

        def dfs(root):
            nonlocal res
            if not root:
                return []
            if root and not root.left and not root.right:
                return [1]
            left, right = dfs(root.left), dfs(root.right)
            right.sort()
            for x in left:
                res += bisect.bisect(right, target - x)
            return [x + 1 for x in left] + [x + 1 for x in right]

        dfs(root)
        return res