Interview Question
Country: United States
Using BFS collect all nodes in queue using BFS;
Travers initial tree using iterQ;
Traverse result tree nodes to append childrens using nextQ;
Here is I am not using getters and setters
I haven't compiled code; i hope it works :)
class Resolve<T> {
Queue<T> iterQ = new LinkedList<>();
Queue<T> nextQ = new LinkedList<>();
private class Node {
T item;
List<Node> children;
public Node(T i, int ch) {
item = i;
children = new ArrayList<Node>(ch)l
}
}
public Node buildNAryTree(Node root, int N) {
Node resNode = new Node(root.item, N);
if (N == 0) {
return resNode;
}
Node curr = root;
Node nextGenRoot = resNode;
while (curr != null) {
Node nextGenCurr = new Node(curr.item, N);
nextQ.offer(nextGenCurr);
nextGenRoot.children.add(nextGenCurr);
if (nextGenRoot.children.size() == N) {
nextGenRoot = nextQ.poll();
}
for(Node n: curr.children) {
iterQ.offer(n)
}
curr = iterQ.poll();
}
}
public static void main (args [] input) {
Resolve<Integer> rr = new Resolve<Integer>();
....
// build tree Node rootOfTree
....
Node rootOfNewTree = rr.buildNAryTree(rootOfTree);
// let say output
}
}
I don't think this can be done. If you need to preserve Ancestry and each interior node other than 1 exception has 0 or N elements, then it can't be done.
See this example. Original tree:
If N were 3, then there is no logical way that you could reorder the tree to have only 0 or 3 children of each node (except for the single exception node) and to preserve ancestry.
Likewise, if the tree were:
And N were 2, there is no way to reorganize the tree such that Ancestry is preserved. You'd have to add extra ancestors in the structural reordering. The tree would have to be something really deformed too like
which is still invalid.
- zortlord July 28, 2015