Swap Nodes in Binary tree of every k'th level - GeeksforGeeks

Swap Nodes in Binary tree of every k'th level - GeeksforGeeks
Given a binary tree and integer value k, the task is to swap sibling nodes of every k'th level where k >= 1.

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.

void Swap( Node **a , Node **b)

{

    Node * temp = *a;

    *a = *b;

    *b = temp;

}

 

// A utility function swap left- node & right node of tree

// of every k'th level

void swapEveryKLevelUtil( Node *root, int level, int k)

{

    // base case

    if (root== NULL ||

            (root->left==NULL && root->right==NULL) )

        return ;

 

    //if current level + 1  is present in swap vector

    //then we swap left & right node

    if ( (level + 1) % k == 0)

        Swap(&root->left, &root->right);

 

    // Recur for left and right subtrees

    swapEveryKLevelUtil(root->left, level+1, k);

    swapEveryKLevelUtil(root->right, level+1, k);

}

 

// This function mainly calls recursive function

// swapEveryKLevelUtil()

void swapEveryKLevel(Node *root, int k)

{

    // call swapEveryKLevelUtil function with

    // initial level as 1.

    swapEveryKLevelUtil(root, 1, k);

}

Read full article from Swap Nodes in Binary tree of every k'th level - GeeksforGeeks