Published
- 1 min read
Given an n-ary tree, return the level order traversal of its nodes values
Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value Input: root = [1,null,3,2,4,null,5,6] Output: [[1],[3,2,4],[5,6]]
Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [[1],[2,3,4,5],[6,7,8,9,10],[11,12,13],[14]]
The input given is confusing, you would be given a node and its children (see the node definition given in the question) Now, you need to find what children belong to same level, that you can solve by incrementing 1 to their parent level
private List<List<Node>> nArrayTreeLevelOrderTraversal(Node root) {
List<List<Node>> finalList = new ArrayList<>();
Map<Integer, List<Node>> map = new HashMap<>();
if(root == null) {
return finalList;
}
Queue<Node> queue = new LinkedList<>();
root.level = 0;
queue.add(root);
while (!queue.isEmpty()) {
Node n = queue.poll();
int level = n.level;
map.computeIfAbsent(level, k -> new ArrayList<>()).add(n);
List<Node> neighbours = n.children;
for(Node neighbour : neighbours) {
neighbour.level = level + 1;
queue.add(neighbour);
}
}
//just print the map
return finalList;
}
private List<List<Node>> nArrayTreeLevelOrderTraversal(Node root) {
List<List<Node>> finalList = new ArrayList<>();
Queue<Node> queue = new LinkedList<>();
List<Node> currentLevelNodes = root.children;
while (currentLevelNodes.size() != 0) {
List<Node> listofNodes = new ArrayList<>();
List<Node> newLevels = new ArrayList<>();
for (Node node : currentLevelNodes) {
listofNodes.add(node);
newLevels.addAll(node.children);
}
finalList.add(listofNodes);
currentLevelNodes = newLevels;
}
return finalList;
}