Given a binary tree and integer value k, the task is to swap sibling nodes of every k’th level where k >= 1.
Input : k = 2 and Root of below tree 1 Level 1 / 2 3 Level 2 / / 4 7 8 Level 3 Output : Root of the following modified tree 1 / 3 2 / / 7 8 4 Explanation : We need to swap left and right sibling every second level. There is only one even level with nodes to be swapped are 2 and 3. Input : k = 1 and Root of following tree 1 Level 1 / 2 3 Level 2 / 4 5 Level 3 Output : Root of the following modified tree 1 / 3 2 / 5 4 Since k is 1, we need to swap sibling nodes of all levels.
A simple solution of this problem is that for each is to find sibling nodes for each multiple of k and swap them.
An efficient solution is to keep track of level number in recursive calls. And for every node being visited, check if level number of its children is a multiple of k. If yes, then swap the two children of the node. Else, recur for left and right children.
Below is the implementation of above idea
Before swap node : 4 2 1 7 3 8 After swap Node : 7 3 8 1 4 2
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.