# Given an N-ary tree pair the leaf nodes such that leaf we are pairing do not have edge used in previous pairing.

• Given an N-ary tree with thousands of nodes, pair the leaf nodes which do NOT SHARE the common path. i.e. Two Leaves can be Paired only if they do NOT have a common edge that was used in a previous pairing.
Source - http://www.geeksforgeeks.org/microsoft-interview-experience-set-56-for-sde-2/
For example,

``````       A
/  |  \
B   C   D
/   / | \
E   F  G  H
``````

Leaf nodes: E, F, G, H & D

Possible Pairs in O/Ps:

1. (E-F), (G-H) or
2. (E-G), (F-H) or
3. (E-H), (F-G) or
4. (E-D), (F-G) or
5. (E-D), (G-H) or
6. (E-D), (F-H) or
7. (D-H), (F-G) or
8. (D-G), (F-H) or
i) (D-F), (G-H)

• so it seems like you are trying to find the permutation of the leaf nodes (and reduce to the closest even number)?

for example:

DEFGH -> DE,FG

DEFHG -> DE,FH

etc...

and make sure a set does not already exist, because ED = DE.

• how to check for common edge in this tree ?

• For whole detailed questions -
http://www.geeksforgeeks.org/microsoft-interview-experience-set-56-for-sde-2/
I'm not able to get the question any help is appreciated....!!!

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