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.
leave a comment
0 Comments