Tutorialspoint.dev

Swap Nodes in Binary tree of every k’th level

Given a binary tree and integer value k, the task is to swap sibling nodes of every k’th level where k >= 1.

Examples:

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

C++

// c++ program swap nodes
#include<bits/stdc++.h>
using namespace std;
  
// A Binary Tree Node
struct Node
{
    int data;
    struct Node *left, *right;
};
  
// function to create a new tree node
Node* newNode(int data)
{
    Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
  
// swap two Node
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);
}
  
// Utility method for inorder tree traversal
void inorder(Node *root)
{
    if (root == NULL)
        return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}
  
// Driver Code
int main()
{
    /*    1
        /  
       2     3
     /      / 
    4      7    8   */
    struct Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->right = newNode(8);
    root->right->left = newNode(7);
  
    int k = 2;
    cout << "Before swap node :"<<endl;
    inorder(root);
  
    swapEveryKLevel(root, k);
  
    cout << " After swap Node :" << endl;
    inorder(root);
    return 0;
}

Java

// Java program swap nodes 
class GFG
{
  
// A Binary Tree Node 
static class Node 
    int data; 
    Node left, right; 
}; 
  
// function to create a new tree node 
static Node newNode(int data) 
    Node temp = new Node(); 
    temp.data = data; 
    temp.left = temp.right = null
    return temp; 
  
  
  
// A utility function swap left- node & right node of tree 
// of every k'th level 
static 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
        {
            Node temp=root.left;
            root.left=root.right;
            root.right=temp;
        }
  
    // 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() 
static void swapEveryKLevel(Node root, int k) 
    // call swapEveryKLevelUtil function with 
    // initial level as 1. 
    swapEveryKLevelUtil(root, 1, k); 
  
// Utility method for inorder tree traversal 
static void inorder(Node root) 
    if (root == null
        return
    inorder(root.left); 
    System.out.print(root.data + " "); 
    inorder(root.right); 
  
// Driver Code 
public static void main(String args[])
    /* 1 
        /  
    2 3 
    / /  
    4 7 8 */
    Node root = newNode(1); 
    root.left = newNode(2); 
    root.right = newNode(3); 
    root.left.left = newNode(4); 
    root.right.right = newNode(8); 
    root.right.left = newNode(7); 
  
    int k = 2
    System.out.println("Before swap node :"); 
    inorder(root); 
  
    swapEveryKLevel(root, k); 
  
    System.out.println(" After swap Node :" ); 
    inorder(root); 
}
  
// This code is contributed by Arnab Kundu

Python

# Python program to swap nodes
  
# A binary tree node
class Node:
  
    # constructor to create a new node  
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
  
# A utility function swap left node and right node of tree
# of every k'th level 
def swapEveryKLevelUtil(root, level, k):
      
    # Base Case 
    if (root is None or (root.left is None and
                        root.right is None ) ):
        return 
  
    # If current level+1 is present in swap vector
    # then we swap left and right node
    if (level+1)%k == 0:
        root.left, root.right = root.right, root.left
      
    # Recur for left and right subtree
    swapEveryKLevelUtil(root.left, level+1, k)
    swapEveryKLevelUtil(root.right, level+1, k)
  
      
# This function mainly calls recursive function
# swapEveryKLevelUtil
def swapEveryKLevel(root, k):
      
    # Call swapEveryKLevelUtil function with 
    # initial level as 1
    swapEveryKLevelUtil(root, 1, k)
  
# Method to find the inorder tree travesal
def inorder(root):
      
    # Base Case
    if root is None:
        return 
    inorder(root.left)
    print root.data, 
    inorder(root.right)
  
# Driver code
"""
          1
        /  
       2     3
     /      / 
    4      7    8 
"""
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.right.right = Node(8)
root.right.left = Node(7)
  
k = 2 
print "Before swap node :" 
inorder(root)
  
swapEveryKLevel(root, k)
  
print " After swap Node : "
inorder(root)
  
# This code is contributed by Nikhil Kumar Singh(nickzuck_007)


Output:

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.



This article is attributed to GeeksforGeeks.org

tags:

Tree Tree

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter