I agree with you specially with the fact that it uses a lot of concepts from the other problems of trees section. I was able to achieve it using a simple algorithm:

1. Build the tree.

2. Repeat below steps for every value of k

   • Perform level order traversal (BFS) of the entire tree.
   • At each level, if level is a multiple of k then swap the
     child of the nodes at that level.
   • After the level order traversal is done, perform in order traversal (DFS) to print the tree nodes data.

I used below definition of a node while building the tree:

class TreeNode
{
    public int Data { get; set; }
    public TreeNode LeftChild {get; set;}
    public TreeNode RightChild { get; set; }
    public int Depth { get; set; }
}