### In C++ Minimum no. of swap to convert Binary Tree to Binary Search Tree

Minimum swap required to convert binary tree to binary search tree

Given the array representation of Complete Binary Tree i.e, if index i is the parent, index 2*i + 1 is the left child and index 2*i + 2 is the right child. The task is to find the minimum number of swap required to convert it into Binary Search Tree.

Examples:

Input : arr[] = { 5, 6, 7, 8, 9, 10, 11 }

Output : 3

Binary tree of the given array:

Swap 1: Swap node 8 with node 5.

Swap 2: Swap node 9 with node 10.

Swap 3: Swap node 10 with node 7.

So, minimum 3 swaps are required.

Input : arr[] = { 1, 2, 3 }

Output : 1

Binary tree of the given array

After swapping node 1 with node 2.

/* C++ program to pairwise swap

leaf nodes from left to right */

#include <bits/stdc++.h>

using namespace std;

// A Binary Tree Node

struct Node

{

int data;

struct Node *left, *right;

};

// function to swap two Node

void Swap(Node **a, Node **b)

{

Node * temp = *a;

*a = *b;

*b = temp;

}

// two pointers to keep track of

// first and second nodes in a pair

Node **firstPtr;

Node **secondPtr;

// function to pairwise swap leaf

// nodes from left to right

void pairwiseSwap(Node **root, int &count)

{

// if node is null, return

if (!(*root))

return;

// if node is leaf node, increment count

if(!(*root)->left&&!(*root)->right)

{

// initialize second pointer

// by current node

secondPtr = root;

// increment count

count++;

// if count is even, swap first

// and second pointers

if (count%2 == 0)

Swap(firstPtr, secondPtr);

else

// if count is odd, initialize

// first pointer by second pointer

firstPtr = secondPtr;

}

// if left child exists, check for leaf

// recursively

if ((*root)->left)

pairwiseSwap(&(*root)->left, count);

// if right child exists, check for leaf

// recursively

if ((*root)->right)

pairwiseSwap(&(*root)->right, count);

}

// Utility 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;

}

// function to print inorder traversal

// of binary tree

void printInorder(Node* node)

{

if (node == NULL)

return;

/* first recur on left child */

printInorder(node->left);

/* then print the data of node */

printf("%d ", node->data);

/* now recur on right child */

printInorder(node->right);

}

// Driver program to test above functions

int main()

{

// Let us create binary tree shown in

// above diagram

Node *root = newNode(1);

root->left = newNode(2);

root->right = newNode(3);

root->left->left = newNode(4);

root->right->left = newNode(5);

root->right->right = newNode(8);

root->right->left->left = newNode(6);

root->right->left->right = newNode(7);

root->right->right->left = newNode(9);

root->right->right->right = newNode(10);

// print inorder traversal before swapping

cout << "Inorder traversal before swap:\n";

printInorder(root);

cout << "\n";

// variable to keep track

// of leafs traversed

int c = 0;

// Pairwise swap of leaf nodes

pairwiseSwap(&root, c);

// print inorder traversal after swapping

cout << "Inorder traversal after swap:\n";

printInorder(root);

cout << "\n";

return 0;

}

Output:

Inorder traversal before swap:

4 2 1 6 5 7 3 9 8 10

Inorder traversal after swap:

6 2 1 4 5 9 3 7 8 10

#### More Articles of Ajay Malik:

Name Views Likes
In C++ Minimum no. of swap to convert Binary Tree to Binary Search Tree 691 23