Complete without any implementations of data structures. Given a complete binary

Question

Complete without any implementations of data structures.

Given a complete binary tree with N nodes and each node have a distinct integer ai attached with it, find the minimum number of swaps you can make to convert the binary tree into binary search tree. In one swap, you can select any two nodes and swap their values. You will be given the array representation of the binary tree. Root of the tree will be at ao Left child of root will be at a1 and right child of root will be at a2. Left child of node at array position k will be at a2%+1 and right child of node at array position k will be at a2%+2. Input format: First line contains an integer, N (1SNs105), denoting the number of nodes. Second line contains N space separated integers, a (1sas105), denoting the value attached to ith node. Output format: Print a single integer, denoting the minimum number of swaps needed to convert binary tree into a binary search tree. Sample Input: 1 23 Sample Output: 1 Explanation We need only one swap (1,2) to convert the given binary tree into binary search tree. 2 3 After swapping (1,2) 2 3

Explanation / Answer

import java.io.*;
import java.util.*;

public class Solution {

public static void main(String[] args) {
Scanner s = new Scanner(System.in);
final int N = s.nextInt();
int[][] leafs = new int[N][2];

for (int i = 0; i < N; i++) {
for (int j = 0; j < 2; j++) {
leafs[i][j] = s.nextInt();
}
}

int[] depths = new int[s.nextInt()];

for (int i = 0; i < depths.length; i++) {
depths[i] = s.nextInt();
}

TreeNode leftTree = (leafs[0][0] > -1) ? new TreeNode(leafs[0][0]) : null;
TreeNode rightTree = (leafs[0][1] > -1) ? new TreeNode(leafs[0][1]) : null;

if (leafs[0][0] > -1) leftTree.mapChildNodes(leftTree, leafs, (leafs[0][0] > -1) ? 1 : 2, 0, N);
if (leafs[0][1] > -1) rightTree.mapChildNodes(rightTree, leafs, (leafs[0][0] > -1) ? 2 : 1, 0, N);

TreeNode mainTree = new TreeNode(1, leftTree, rightTree);

for(int d : depths) {
mainTree.swap(mainTree, d, 1);
mainTree.inorder(mainTree);
System.out.println();
}   
}
}

class TreeNode {
private int data;
private TreeNode left;
private TreeNode right;

TreeNode(int data) {
this.data = data;
}

TreeNode(int data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}

private void insertLeft(int data) {
if (this.left == null) {
this.left = new TreeNode(data);
} else {
this.left.insertLeft(data);
}
}
private void insertRight(int data) {
if (this.right == null) {
this.right = new TreeNode(data);
} else {
this.right.insertRight(data);
}
}

public void inorder(TreeNode node) {
if (node == null) return;

inorder(node.left);
System.out.print(node.toString());
inorder(node.right);
}

public void mapChildNodes(TreeNode node, int[][] leafs, int i, int j, int arraySize) {
if (arraySize == 0) return;

if (leafs[i][j] > -1){
node.insertLeft(leafs[i][j]);
mapChildNodes(node.left, leafs, leafs[i][j]-1, 0, arraySize-1);
}
if (leafs[i][j+1] > -1){
node.insertRight(leafs[i][j+1]);
mapChildNodes(node.right, leafs, leafs[i][j+1]-1, 0, arraySize-1);
}  
}

public void swap(TreeNode node, int targetDepth, int depth) {
if(node == null) return;

if(depth % targetDepth == 0) {
TreeNode temp = node.left;
node.left = node.right;
node.right = temp;
}
swap(node.left, targetDepth, depth+1);
swap(node.right, targetDepth, depth+1);

}

@Override
public String toString() {
return this.data + " ";
}
}

import java.util.Scanner;

public class Solution {
public static final int ROOT_NODE = 1;

public static void main(String[] args) {
Scanner s = new Scanner(System.in);
final int N = s.nextInt();
int[][] tree = new int[N+ROOT_NODE][2];

for (int i = ROOT_NODE; i < N+ROOT_NODE; i++) {
for (int j = 0; j < 2; j++) {
tree[i][j] = s.nextInt();
}
}

int numDepths = s.nextInt();
for (int i = 0; i < numDepths; i++) {
swap(tree, ROOT_NODE, s.nextInt(), 1);
System.out.println();
}
}

public static void swap(int [][] tree, int node, int targetDepth,
int depth) {
if(node == -1) return;

if(depth % targetDepth == 0) {
int temp = tree[node][0];
tree[node][0] = tree[node][1];
tree[node][1] = temp;
}
swap(tree, tree[node][0], targetDepth, depth+1);
System.out.print(Integer.toString(node) + " ");
swap(tree, tree[node][1], targetDepth, depth+1);
}
}

void swapNodes(BSTNode *node1, BSTNode *node2)
{
if(node1->parent->left==node1)
node1->parent->left = node2;
else
node1->parent->right = node2;
if(node2->parent->left==node2)
node2->parent->left = node1;
else
node2->parent->right = node1;

BSTNode *temp;
temp->parent = node1->parent;
temp->left = node1->left;
temp->right = node1->right;

node1->parent = node2->parent;
node1->left = node2->left;
node1->right = node2->right;

node2->parent = temp->parent;
node2->left = temp->left;
node2->right = temp->right;
}
void Swap(T* aP,T* aQ)
{
T* new_p_parent = aQ->iParent;
T* new_p_left = aQ->iLeft;
T* new_p_right = aQ->iRight;
T** new_p_link = &iRoot;
if (aQ->iParent)
new_p_link = aQ->iParent->iLeft == aQ ? &aQ->iParent->iLeft : &aQ->iParent->iRight;

T* new_q_parent = aP->iParent;
T* new_q_left = aP->iLeft;
T* new_q_right = aP->iRight;
T** new_q_link = &iRoot;
if (aP->iParent)
new_q_link = aP->iParent->iLeft == aP ? &aP->iParent->iLeft : &aP->iParent->iRight;

if (aQ->iParent == aP)
{
new_p_parent = aQ;
new_p_link = nullptr;
if (aP->iLeft == aQ)
new_q_left = aP;
else
new_q_right = aP;
}
else if (aP->iParent == aQ)
{
new_q_parent = aP;
new_q_link = nullptr;
if (aQ->iLeft == aP)
new_p_left = aQ;
else
new_p_right = aQ;
}

aP->iParent = new_p_parent;
aP->iLeft = new_p_left;
if (aP->iLeft)
aP->iLeft->iParent = aP;
aP->iRight = new_p_right;
if (aP->iRight)
aP->iRight->iParent = aP;
if (new_p_link)
*new_p_link = aP;

aQ->iParent = new_q_parent;
aQ->iLeft = new_q_left;
if (aQ->iLeft)
aQ->iLeft->iParent = aQ;
aQ->iRight = new_q_right;
if (aQ->iRight)
aQ->iRight->iParent = aQ;
if (new_q_link)
*new_q_link = aQ;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.