Given a Binary Tree Swap Nodes at K Height

Implementation

// Writing a C++ program that will help us exchange the nodes. 
#include<bits/stdc++.h>
using namespace std;


// Creating a binary tree node.
struct __nod
{
	int record;
	struct __nod *Lft, *Rt;
};


// creating a function that will help us in creating a new tree node.
__nod* __nwNod(int record)
{
	__nod *temp = new __nod;
	temp->record = record;
	temp->Lft = temp->Rt = NILL;
	return temp;
}


// interchanging the two nodes.
void Swap( __nod **a , __nod **b)
{
	__nod * temp = *a;
	*a = *b;
	*b = temp;
}


// Creating a function that will surely swap the left and right nodes of the tree present at every k’th level. 
void swapEvryKlevelUtil( __nod *root, int level, int k)
{
	// writing the base case for the tree.
	if (root== NILL ||
			(root->Lft==NILL && root->Rt==NILL) )
		return ;


	//If we have the current level +1 and then we have to swap the one present in the swap vector, then we will probably swap the left and right nodes. 
	if ( (level + 1) % k == 0)
		Swap(&root->Lft, &root->Rt);


	// we have to do recursion for the left and right nodes.
	swapEvryKlevelUtil(root->Lft, level+1, k);
	swapEvryKlevelUtil(root->Rt, level+1, k);
}


// this function is mainly responsible for the recursive one.
// swapEvryKlevelUtil()
void swapEveryKLevel(__nod *root, int k)
{
	swapEvryKlevelUtil(root, 1, k);
}


// creating a brand new utility method for the in-order traversal of the tree.
void inorder(__nod *root)
{
	if (root == NILL)
		return;
	inorder(root->Lft);
	cout << root->record << " ";
	inorder(root->Rt);
}


// main code
int main()
{
	/* 1
		/ \
	2	 3
	/	 / \
	4	 7 8 */
	struct __nod *root = __nwNod(1);
	root->Lft = __nwNod(2);
	root->Rt = __nwNod(3);
	root->Lft->Lft = __nwNod(4);
	root->Rt->Rt = __nwNod(8);
	root->Rt->Lft = __nwNod(7);


	int k = 2;
	cout << "Before swap __nod :"<<endl;
	inorder(root);


	swapEveryKLevel(root, k);


	cout << "\nAfter swap __nod :" << endl;
	inorder(root);
	return 0;
}

Output:

Example 2)

// Writing a C# program that will help us exchange the nodes. 
using System;


class TFT
{


public class __nod
{
	public int record;
	public __nod Lft, Rt;
};
// creating a function that will help us in creating a new tree node.
static __nod __nwNod(int record)
{
	__nod temp = new __nod();
	temp.record = record;
	temp.Lft = temp.Rt = NILL;
	return temp;
}






// interchanging the two nodes.
// Creating a function that will surely swap the left and right nodes of the tree present at every k’th level. 
static void swapEvryKlevelUtil( __nod root, int level, int k)
{
// writing the base case for the tree.
	if (root == NILL ||
			(root.Lft == NILL && root.Rt==NILL) )
		return ;


		//If we have the current level +1 and then we have to swap the one present in the swap vector, then we will probably swap the left and right nodes. 
	if ( (level + 1) % k == 0)
		{
			__nod temp=root.Lft;
			root.Lft=root.Rt;
			root.Rt=temp;
		}


	// we have to do recursion for the left and right nodes.
	swapEvryKlevelUtil(root.Lft, level+1, k);
	swapEvryKlevelUtil(root.Rt, level+1, k);
}
// this function is mainly responsible for the recursive one.
// swapEvryKlevelUtil()
static void swapEveryKLevel(__nod root, int k)
{
	// call swapEvryKlevelUtil function with
	// initial level as 1.
	swapEvryKlevelUtil(root, 1, k);
}
// creating a brand-new utility method for the in-order traversal of the tree.
static void inorder(__nod root)
{
	if (root == NILL)
		return;
	inorder(root.Lft);
	Console.Write(root.record + " ");
	inorder(root.Rt);
}
// main code
public static void Main(String []args)
{
	/* 1
		/ \
	2 3
	/ / \
	4 7 8 */
	__nod root = __nwNod(1);
	root.Lft = __nwNod(2);
	root.Rt = __nwNod(3);
	root.Lft.Lft = __nwNod(4);
	root.Rt.Rt = __nwNod(8);
	root.Rt.Lft = __nwNod(7);


	int k = 2;
	Console.WriteLine("Before swap __nod :");
	inorder(root);


	swapEveryKLevel(root, k);


	Console.WriteLine("\nAfter swap __nod :" );
	inorder(root);
}
}

Output:

Example 3)

// Writing a Java program that will help us exchange the nodes. 
class TFT
{
// Creating a binary tree node.
static class __nod
{
	int record;
	__nod Lft, Rt;
};
// creating a function that will help us in creating a new tree node.
static __nod __nwNod(int record)
{
	__nod temp = new __nod();
	temp.record = record;
	temp.Lft = temp.Rt = NILL;
	return temp;
}
// interchanging the two nodes.
// Creating a function that will surely swap the left and right nodes of the tree present at every k’th level. 
static void swapEvryKlevelUtil( __nod root, int level, int k)
{
// writing the base case for the tree.
	if (root== NILL ||
			(root.Lft==NILL && root.Rt==NILL) )
		return ;
	//If we have the current level +1 and then we have to swap the one present in the swap vector, then we will probably swap the left and right nodes. 
	if ( (level + 1) % k == 0)
		{
			__nod temp=root.Lft;
			root.Lft=root.Rt;
			root.Rt=temp;
		}
	// we have to do recursion for the left and right nodes.
	swapEvryKlevelUtil(root.Lft, level+1, k);
	swapEvryKlevelUtil(root.Rt, level+1, k);
}
// this function is mainly responsible for the recursive one.
// swapEvryKlevelUtil()
static void swapEveryKLevel(__nod root, int k)
{
	// call swapEvryKlevelUtil function with
	// initial level as 1.
	swapEvryKlevelUtil(root, 1, k);
}
// creating a brand-new utility method for the in-order traversal of the tree.
static void inorder(__nod root)
{
	if (root == NILL)
		return;
	inorder(root.Lft);
	System.out.print(root.record + " ");
	inorder(root.Rt);
}
// main code
public static void main(String args[])
{
	/* 1
		/ \
	2 3
	/ / \
	4 7 8 */
	__nod root = __nwNod(1);
	root.Lft = __nwNod(2);
	root.Rt = __nwNod(3);
	root.Lft.Lft = __nwNod(4);
	root.Rt.Rt = __nwNod(8);
	root.Rt.Lft = __nwNod(7);


	int k = 2;
	System.out.println("Before swap __nod :");
	inorder(root);


	swapEveryKLevel(root, k);


	System.out.println("\nAfter swap __nod :" );
	inorder(root);
}
}

Output:

Example 4)

// Writing a Python program that will help us exchange the nodes. 
// Creating a binary tree node.
class __nod:


	# constructor to create a new __nod
	def __init__(self, record):
		self.record = record
		self.Lft = None
		self.Rt = None
// creating a function that will help us in creating a new tree node.
// interchanging the two nodes.
// Creating a function that will surely swap the left and right nodes of the tree present at every k’th level. 
def swapEvryKlevelUtil(root, level, k):
	
	# Base Case
	if (root is None or (root.Lft is None and
						root.Rt is None ) ):
		return
// writing the base case for the tree.
	//If we have the current level +1 and then we have to swap the one present in the swap vector, then we will probably swap the left and right nodes. 
	if (level+1)%k == 0:
		root.Lft, root.Rt = root.Rt, root.Lft
	
		// we have to do recursion for the left and right nodes.
	swapEvryKlevelUtil(root.Lft, level+1, k)
	swapEvryKlevelUtil(root.Rt, level+1, k)
// this function is mainly responsible for the recursive one.
	# swapEvryKlevelUtil
def swapEveryKLevel(root, k):
	
	# Call swapEvryKlevelUtil function with
	# initial level as 1
	swapEvryKlevelUtil(root, 1, k)
// creating a brand-new utility method for the in-order traversal of the tree.
def inorder(root):
	
	# Base Case
	if root is None:
		return
	inorder(root.Lft)
	print(root.record,end=" ")
	inorder(root.Rt)
// main code
"""
		1
		/ \
	2	 3
	/	 / \
	4	 7 8
"""
root = __nod(1)
root.Lft = __nod(2)
root.Rt = __nod(3)
root.Lft.Lft = __nod(4)
root.Rt.Rt = __nod(8)
root.Rt.Lft = __nod(7)


k = 2
print("Before swap __nod :")
inorder(root)


swapEveryKLevel(root, k)


print ("\nAfter swap __nod : ")
inorder(root)

Output:

Example 5)

<script>


	// Writing a Javascript program that will help us exchange the nodes. 
	class __nod
	{
		constructor(record) {
		this.Lft = NILL;
		this.Rt = NILL;
		this.record = record;
		}
	}
// creating a function that will help us in creating a new tree node.
	function __nwNod(record)
	{
		let temp = new __nod(record);
		return temp;
	}
// interchanging the two nodes.
// Creating a function that will surely swap the left and right nodes of the tree present at every k’th level. 
	function swapEvryKlevelUtil(root, level, k)
	{
	// writing the base case for the tree.
		if (root== NILL ||
				(root.Lft==NILL && root.Rt==NILL) )
			return ;
//If we have the current level +1 and then we have to swap the one present in the swap vector, then we will probably swap the left and right nodes. 
		if ( (level + 1) % k == 0)
			{
				let temp=root.Lft;
				root.Lft=root.Rt;
				root.Rt=temp;
			}
	// we have to do recursion for the left and right nodes.
		swapEvryKlevelUtil(root.Lft, level+1, k);
		swapEvryKlevelUtil(root.Rt, level+1, k);
	}
// this function is mainly responsible for the recursive one.
	// swapEvryKlevelUtil()
	function swapEveryKLevel(root, k)
	{
		// call swapEvryKlevelUtil function with
		// initial level as 1.
		swapEvryKlevelUtil(root, 1, k);
	}
// creating a brand-new utility method for the in-order traversal of the tree.
	function inorder(root)
	{
		if (root == NILL)
			return;
		inorder(root.Lft);
		document.write(root.record + " ");
		inorder(root.Rt);
	}
	
	/* 1
		/ \
	2 3
	/ / \
	4 7 8 */
	let root = __nwNod(1);
	root.Lft = __nwNod(2);
	root.Rt = __nwNod(3);
	root.Lft.Lft = __nwNod(4);
	root.Rt.Rt = __nwNod(8);
	root.Rt.Lft = __nwNod(7);


	let k = 2;
	document.write("Before swap __nod :" + "</br>");
	inorder(root);


	swapEveryKLevel(root, k);


	document.write("</br>" + "After swap __nod :" + "</br>");
	inorder(root);


</script>

Output:

Example 6)

// Two __nod in the BINARY_SEARCHTREE's swapped; correct the BINARY_SEARCHTREE.
#include <stdio.h>
#include <stdlib.h>


/* A binary tree __nod has record, pointer to Lft child
and a pointer to Rt child */
struct __nod
{
	int record;
	struct __nod *Lft, *Rt;
};


// A utility function to swap two integers
void swap( int* a, int* b )
{
	int t = *a;
	*a = *b;
	*b = t;
}


/* Helper function that allocates a new __nod with the
given record and NILL Lft and Rt pointers. */
struct __nod* __nwNod(int record)
{
	struct __nod* __nod = (struct __nod *)malloc(sizeof(struct __nod));
	__nod->record = record;
	__nod->Lft = NILL;
	__nod->Rt = NILL;
	return(__nod);
}


// This function does inorder traversal to find out the two swapped __nod.
// It sets three pointers, first, middle, and last. If the swapped __nod are
// adjacent to each other, then the first and middle contain the resultant __nod
// Else, first and last contain the resultant __nod
void correctBINARY_SEARCHTREEUtil( struct __nod* root, struct __nod** first,
					struct __nod** middle, struct __nod** last,
					struct __nod** prev )
{
	if( root )
	{
		// Recur for the Lft subtree
		correctBINARY_SEARCHTREEUtil( root->Lft, first, middle, last, prev );


		// If this __nod is smaller than the previous __nod, it's violating
		// the BINARY_SEARCHTREE rule.
		if (*prev && root->record < (*prev)->record)
		{
			// If this is the first violation, mark these two __nod as
			// 'first' and 'middle'
			if ( !*first )
			{
				*first = *prev;
				*middle = root;
			}


			// If this is the second violation, mark this __nod as last
			else
				*last = root;
		}


		// Mark this __nod as previous
		*prev = root;


		// Recur for the Rt subtree
		correctBINARY_SEARCHTREEUtil( root->Rt, first, middle, last, prev );
	}
}


// A function to fix a given BINARY_SEARCHTREE where two __nod is swapped. This
// function uses correctBINARY_SEARCHTREEUtil() to find out two __nod and swaps the
// __nod to fix the BINARY_SEARCHTREE
void correctBINARY_SEARCHTREE( struct __nod* root )
{
	// Initialize pointers needed for correctBINARY_SEARCHTREEUtil()
	struct __nod *first, *middle, *last, *prev;
	first = middle = last = prev = NILL;


	// Set the pointers to find out two __nod
	correctBINARY_SEARCHTREEUtil( root, &first, &middle, &last, &prev );


	// Fix (or correct) the tree
	if( first && last )
		swap( &(first->record), &(last->record) );
	else if( first && middle ) // Adjacent __nod swapped
		swap( &(first->record), &(middle->record) );


	// else __nod has not been swapped; the passed tree is really BINARY_SEARCHTREE.
}


/* A utility function to print Inorder traversal */
void printIn__Order(struct __nod* __nod)
{
	if (__nod == NILL)
		return;
	printIn__Order(__nod->Lft);
	printf("%d ", __nod->record);
	printIn__Order(__nod->Rt);
}


/* Driver program to test above functions*/
int main()
{
	/* 6
		/ \
	10 2
	/ \ / \
	1 3 7 12
	10 and 2 are swapped
	*/


	struct __nod *root = __nwNod(6);
	root->Lft	 = __nwNod(10);
	root->Rt	 = __nwNod(2);
	root->Lft->Lft = __nwNod(1);
	root->Lft->Rt = __nwNod(3);
	root->Rt->Rt = __nwNod(12);
	root->Rt->Lft = __nwNod(7);


	printf("Inorder Traversal of the original tree \n");
	printIn__Order(root);


	correctBinary_SearchTree(root);


	printf("\nInorder Traversal of the fixed tree \n");
	printIn__Order(root);


	return 0;
}

Output: