# Find all leaf node pairs which do not share common path in a N-ary tree

• Re: Given an N-ary tree pair the leaf nodes such that leaf we are pairing do not have edge used in previous pairing. @codersx
This is the round 1 question 2 in this post.
Below is my solution. The basic idea is:

1. Build a hash map contains all edges to store the used state.
2. Build a list contains all edges along the root-leaf path for each leaf.
3. Enumerate all leaf nodes, find out every set of valid leaf pairs, please see my comments for explanations.
``````class NTreeNode
{
public:
NTreeNode(string defaultVal) : val{ defaultVal } {}
string val;
vector<NTreeNode *> children;
};

namespace std
{
template <>
struct hash<pair<NTreeNode *, NTreeNode *>> : public unary_function<pair<NTreeNode *, NTreeNode *>, size_t>
{
size_t operator()(const pair<NTreeNode *, NTreeNode *> &value) const
{
size_t node1 = (size_t)value.first, node2 = (size_t)value.second;
return (size_t)(node1 ^ node2);
}
};

template <>
struct equal_to<pair<NTreeNode *, NTreeNode *>> : public unary_function<pair<NTreeNode *, NTreeNode *>, bool>
{
bool operator()(const pair<NTreeNode *, NTreeNode *> &x, const pair<NTreeNode *, NTreeNode *> &y) const
{
return x.first == y.first && x.second == y.second;
}
};
}

class G4G_MS_Set56_R1Q2 {
public:
vector<unordered_set<pair<NTreeNode*, NTreeNode*>>> findDisjontLeafPairs(NTreeNode *root) {
// build edge hash map
unordered_map<pair<NTreeNode *, NTreeNode *>, int> edgeUsageMap;
buildEdgeUsageMap(root, edgeUsageMap);

// build edge list for each leaf node
vector<pair<NTreeNode *, NTreeNode *>> edgeList;
unordered_map<NTreeNode *, vector<pair<NTreeNode *, NTreeNode *>>> edgeListMap;
vector<NTreeNode *> leaves;
buildRootToLeafEdgeListMap(root, edgeList, edgeListMap, leaves);

// Recursively enumerate all leaf pairs find valid sets
vector<unordered_set<pair<NTreeNode*, NTreeNode*>>> validLeafPairSet;
vector<pair<NTreeNode*, NTreeNode*>> currentLeafPairs;
findAllValidLeafPairs(leaves, edgeListMap, edgeUsageMap, currentLeafPairs, validLeafPairSet);
return validLeafPairSet;
}
private:
const int USED = 1;
const int FREE = 0;

void buildEdgeUsageMap(NTreeNode *root, unordered_map<pair<NTreeNode *, NTreeNode *>, int> &map) {
queue<NTreeNode *> q;
q.push(root);
while (!q.empty()) {
NTreeNode *node = q.front();
q.pop();
for (auto child : node->children) {
map.emplace(make_pair(node, child), 0);
q.push(child);
}
}
}

void buildRootToLeafEdgeListMap(
NTreeNode *node,
vector<pair<NTreeNode *, NTreeNode *>> &edgeList,
unordered_map<NTreeNode *, vector<pair<NTreeNode *, NTreeNode *>>> &map,
vector<NTreeNode *> &leaves) {
if (node->children.empty()) {
map[node] = edgeList;
leaves.emplace_back(node);
}
else {
for (auto child : node->children) {
edgeList.emplace_back(make_pair(node, child));
buildRootToLeafEdgeListMap(child, edgeList, map, leaves);
edgeList.pop_back();
}
}
}

void findAllValidLeafPairs(
vector<NTreeNode *> leaves,
unordered_map<NTreeNode *, vector<pair<NTreeNode *, NTreeNode *>>> &edgeListMap,
unordered_map<pair<NTreeNode *, NTreeNode *>, int> &edgeUsageMap,
vector<pair<NTreeNode*, NTreeNode*>> &currentLeafPairs,
vector<unordered_set<pair<NTreeNode*, NTreeNode*>>> &validLeafPairSet) {
if (leaves.empty() || leaves.size() == 1) {
// Give some node not picked, the rest nodes may form a set which is a subset of when that node was picked, this is not a valid solution.
// E.g. given leaves {A, B, C, D}, after considered combination (A, B), (A, C), (A, D), we may want try pairs in {B, C, D} without A picked,
// however, if we pick (B, C), D may or may not be able to pair with A, if D can pair with A, then (B, C) is just a subset of {(B, C), {A, D)},
// if A & D cannot pair given B, C selected, then {(B, C)} is a valid solution.
if (!IsSubsetOfExistingLeafPairSet(currentLeafPairs, validLeafPairSet)) {
validLeafPairSet.emplace_back(unordered_set<pair<NTreeNode*, NTreeNode*>>(currentLeafPairs.begin(), currentLeafPairs.end()));
}
}
else {
NTreeNode *node = leaves[0];
leaves.erase(leaves.begin());
for (int i = 0; i < leaves.size(); i++) {
NTreeNode *node2 = leaves[i];
if (checkEdgeUsage(node, node2, edgeListMap, edgeUsageMap)) {
setEdgeUsage(node, node2, edgeListMap, edgeUsageMap, USED);
currentLeafPairs.emplace_back(make_pair(node, node2));
leaves.erase(leaves.begin() + i);
findAllValidLeafPairs(leaves, edgeListMap, edgeUsageMap, currentLeafPairs, validLeafPairSet);
leaves.insert(leaves.begin() + i, node2);
currentLeafPairs.pop_back();
setEdgeUsage(node, node2, edgeListMap, edgeUsageMap, FREE);
}
}

//  We should also try the combinations without the first node picked
findAllValidLeafPairs(leaves, edgeListMap, edgeUsageMap, currentLeafPairs, validLeafPairSet);
}
}

bool checkEdgeUsage(
NTreeNode * node1,
NTreeNode * node2,
unordered_map<NTreeNode *, vector<pair<NTreeNode *, NTreeNode *>>> &edgeListMap,
unordered_map<pair<NTreeNode *, NTreeNode *>, int> &edgeUsageMap) {
auto edge_it1 = edgeListMap[node1].begin();
auto edge_it2 = edgeListMap[node2].begin();
// If the 2 path shares some edges in the beginning, we bypass these edges, since they are above the LCA of the 2 nodes.
// E.g. A->B->C->E ->F and  A->B->C->D are paths from root to leaves F and D, we can ignore the common path A->B->C,
// since from F to D, we only need go via the the LCA node C, and only edges C->E, E->F and C->D will be used.
while ((*edge_it1).first == (*edge_it2).first && (*edge_it1).second == (*edge_it2).second) {
edge_it1++;
edge_it2++;
}

bool isUsed = false;
for (; edge_it1 != edgeListMap[node1].end(); edge_it1++) {
if (edgeUsageMap[*edge_it1] == USED) {
isUsed = true;
break;
}
}

if (!isUsed)
{
for (; edge_it2 != edgeListMap[node2].end(); edge_it2++) {
if (edgeUsageMap[*edge_it2] == USED) {
isUsed = true;
break;
}
}
}
return !isUsed;
}

void setEdgeUsage(
NTreeNode * node1,
NTreeNode * node2,
unordered_map<NTreeNode *, vector<pair<NTreeNode *, NTreeNode *>>> &edgeListMap,
unordered_map<pair<NTreeNode *, NTreeNode *>, int> &edgeUsageMap,
int state) {
auto edge_it1 = edgeListMap[node1].begin();
auto edge_it2 = edgeListMap[node2].begin();
// Same idea with checkEdgeUsage.
while ((*edge_it1).first == (*edge_it2).first && (*edge_it1).second == (*edge_it2).second) {
edge_it1++;
edge_it2++;
}
for (; edge_it1 != edgeListMap[node1].end(); edge_it1++) {
edgeUsageMap[*edge_it1] = state;
}
for (; edge_it2 != edgeListMap[node2].end(); edge_it2++) {
edgeUsageMap[*edge_it2] = state;
}
}

bool IsSubsetOfExistingLeafPairSet(vector<pair<NTreeNode*, NTreeNode*>> &currentLeafPairs, vector<unordered_set<pair<NTreeNode*, NTreeNode*>>> &validLeafPairSet) {
bool isSubset = false;
for (auto leafSet : validLeafPairSet) {
isSubset = true;
for (auto leafPair : currentLeafPairs) {
if (leafSet.find(leafPair) == leafSet.end()) {
isSubset = false;
break;
}
}
if (isSubset) {
break;
}
}
return isSubset;
}
};

void Print(vector<unordered_set<pair<NTreeNode*, NTreeNode*>>> &validLeafPairSet) {
for (auto pairSet : validLeafPairSet) {
for (auto pair : pairSet) {
cout << '(' << pair.first->val << ',' << pair.second->val << "), ";
}
cout << endl;
}
cout << "Total:" << validLeafPairSet.size()<<endl;
}

int main()
{
NTreeNode *root = new NTreeNode("A");
root->children = { new NTreeNode("B"), new NTreeNode("C"), new NTreeNode("D") };
root->children[0]->children = { new NTreeNode("E") };
root->children[1]->children = { new NTreeNode("F"),new NTreeNode("G"),new NTreeNode("H") };
G4G_MS_Set56_R1Q2 worker;
Print(worker.findDisjontLeafPairs(root));

root = new NTreeNode("A");
root->children = { new NTreeNode("B"), new NTreeNode("C"), new NTreeNode("D") };
Print(worker.findDisjontLeafPairs(root));

root = new NTreeNode("A");
root->children = { new NTreeNode("B"), new NTreeNode("C"), new NTreeNode("D"), new NTreeNode("E") };
Print(worker.findDisjontLeafPairs(root));

root = new NTreeNode("A");
root->children = { new NTreeNode("B") };
root->children[0]->children = { new NTreeNode("C"), new NTreeNode("D") };
root->children[0]->children[0]->children = { new NTreeNode("E"), new NTreeNode("F") };
root->children[0]->children[0]->children[0]->children = { new NTreeNode("G"), new NTreeNode("H") };
Print(worker.findDisjontLeafPairs(root));
return 0;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.