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