gistfile1.java

class KArayTree {
    private Node bfs(List<Node> preOrder, int k){
        Node root = preOrder.get(0);
        Deque<Node> q = new ArrayDeque<>();
        q.addLast(root);
        int index=1;
        while(!q.isEmpty()){
            Node p = q.removeFirst();
            p.deleteAllChildren();
            for(int i=0;i<k;i++){
                if(index>=preOrder.size())
                    return root;
                p.addChild(preOrder.get(index));
                q.addLast(preOrder.get(index));
                index++;
            }
        }
        return root;
    }

    private List<Node> preOrder(Node root){
        List<Node> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    private void dfs(Node root, List<Node> res){
        if(root==null)
            return;
        res.add(root);
        for(Node c: root.getAllChildren())
            dfs(c, res);
    }

    public Node completeKAryTree(Node root, int k){
        if(root==null)
            return null;
        return bfs(preOrder(root), k);
    }
}