Logo
×

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:

Given a Binary Tree Swap Nodes at K Height

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:

Given a Binary Tree Swap Nodes at K Height

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:

Given a Binary Tree Swap Nodes at K Height

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:

Given a Binary Tree Swap Nodes at K Height

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:

Given a Binary Tree Swap Nodes at K Height

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:

Given a Binary Tree Swap Nodes at K Height

Related Topics

Dynamic memory allocation of structure in C

We can normally store elements of the same datatype with the help of an array in C programming. We can store multiple numbers of elements of a character data type...

5 minutes read.

Circular Linked List

Circular Linked List A circular linked list where all nodes are connected to their next node and last node is connected to the starting node or we can say all nodes...

5 minutes read.

Segregate Even and Odd nodes in a Linked List

Segregate even and odd nodes in a Linked List In this problem, we have given a linked list with integer numbers. We need to modify the given linked list in such...

4 minutes read.

Delete nodes from the linked list which have a greater value on the right side

Delete nodes from the linked list which have a greater value on the right side In this problem, we have given a singly linked list, and we need to remove all...

3 minutes read.

Detect and Remove Loop in a Linked List

Create a function called detectAndRemovetheLoop() that verifies whether a given Linked List has a loop, eliminates the loop if it does, and returns true if it does. It returns false...

6 minutes read.

B Tree vs B + Tree: Data Structure

Difference Between B Tree and B+ Tree What is B Tree? B-Tree is a self-balancing or special type of m-way tree. B-Trees are used mainly in disc access. If we want...

3 minutes read.

Print kth least significant bit number

You have given a number and you have to find out the kth least significant bit of this number. K will be given to you.  The bit will be from...

3 minutes read.

Rearrange a linked list into alternate fashion first and the last element

Rearrange a linked list into alternate fashion first and the last element This article will explain how to rearrange the linked list into alternate fashion first and the last element. Here,...

3 minutes read.

Assembly Line Scheduling

If we take an example of a car factory, there are two assembly lines. In an assembly line, we can assemble and repair the parts of a car. Now, suppose...

5 minutes read.

What is a Tree in Terms of a Graph?

To know the explanation of trees in terms of graphs, we need first to know what trees and graphs are. So let us first learn about trees and graphs. Trees and...

6 minutes read.

What is a Height-Balanced Tree in Data Structure

A height-balanced tree is a type of binary tree. If the absolute difference between the heights of the left and right subtree is less than or equal to 1, then...

6 minutes read.

Introduction to Arrays

What exactly is an array? A group of related data pieces stored in contiguous memory regions is referred to as an array. It is the most basic data structure in which...

5 minutes read.

Find Bridges in a Graph

You have been given a graph. You have to find out the bridges in that graph. Graph may be connected or disconnected. You have to print vertices of particular edge...

4 minutes read.

Applications of trees in data structures

Data structures Storage used to organize and store data is known as the data structure. It is a method of managing computerized data to translate or retrieve it more efficiently. A...

7 minutes read.

Selection Sort

In each iteration of the selection sort algorithm, the smallest item from an unsorted list is chosen and placed at the top of the unsorted list. Algorithm of Selection Sorting In order...

3 minutes read.

Function to Create a Copy of Binary Search Tree

Implementation // creating a new hashmap in the language C++ that will help us clone a binary tree with arbitrary pointers.  #include<iostream> #include<unordered_map> using namespace std; /* A given binary tree has a record, a...

9 minutes read.

Linear vs Circular Queue: Data Structure

Difference Between Linear and Circular Queue What is Linear Queue? A linear queue is linear data structure which works on first in first out principle. We can say a linear queue is...

3 minutes read.

Function to Insert a Node in a Binary Search Tree

Implementation // writing C++ code that will help us in implementing the insertion operation in a binary search tree. #include <bits/stdc++.h> using namespace std; // creating a new binary search tree node struct __nod { int...

8 minutes read.

Fundamental of Algorithms

An algorithm is a part of any programming solution or coding. If we have to make a solution then first we have to think of a clear idea about the...

13 minutes read.

B Tree in Data Structure

Data management is called database management. A data model is a system that stores, manages, and optimizes computer resources. Data processing is not just about data storage. Almost every app...

9 minutes read.