joshita / dev

Published

- 1 min read

Given an n-ary tree, return the level order traversal of its nodes values

img of 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;
    }