HackerRank Swap Nodes [Algo] problem solution

YASH PAL,

In this HackerRank Swap Nodes [Algo] interview preparation kit problem You are given a tree of n nodes where nodes are indexed from [1..n] and it is rooted at 1. You have to perform t swap operations on it and after each swap operation print the in-order traversal of the current state of the tree.

HackerRank Swap Nodes [Algo] Interview preparation kit solution

Problem solution in Python programming.

from collections import deque

class Node:
    def __init__(self, index):
        self.left = None
        self.right = None
        self.index = index
        
    
def in_order_traverse(root):
    """Don't use recursion b/c of recursion limit."""
    stack = deque([root])
    visited = set()
    while stack:
        node = stack.pop()
        if node is None:
            continue
        if node.index in visited:
            print(node.index, end=' ')
            continue
        visited.add(node.index)
        stack.append(node.right)
        stack.append(node)
        stack.append(node.left)
    
    
def swap(root, k):
    """Don't use recursion b/c of recursion limit."""
    q = deque([(root, 1)])
    while q:
        node, level = q.popleft()
        if node is None:
            continue
        if level % k == 0:
            node.left, node.right = node.right, node.left
        q.append((node.left, level+1))
        q.append((node.right, level+1))

        
        
# get number of nodes    
N = int(input())

# create node list
nodes = [None]*(N+1)
for i in range(1, N+1):
    n = Node(i)
    n.left_index, n.right_index = [v if v > 0 else 0 for v in map(int, input().split())]
    nodes[i] = n

# fill out node objects
for n in nodes[1:]:
    left = nodes[n.left_index]
    right = nodes[n.right_index]
    n.left = left
    n.right = right

T = int(input())
root = nodes[1]
# do the swapping
for _ in range(T):
    k = int(input())
    swap(root, k)
    in_order_traverse(root)
    print('')

Problem solution in Java Programming.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

import java.util.*;

public class Solution{
    static Node root = new Node(1);

    public static void main(String ... arg)
    {
        Scanner sc = new Scanner(System.in);
        int n,t,k;
        n = sc.nextInt();
        int[][] tree = new int[n][2];
        for(int i=0;i<n;i++)
        {
            tree[i][0] = sc.nextInt();
            tree[i][1] = sc.nextInt();
        } 
        root = ConstuctTree(tree);
        t = sc.nextInt();
        while(t-->0)
        {
            k = sc.nextInt();
            levelWise(root,k);
            InOrderRec(root);
            System.out.println();
        }
    }

    public static void levelWise(Node root,int k)
    {
        Stack<Node> currentlevel = new Stack<>();
        Stack<Node> nextlevel = new Stack<>();
        int level=1;
        Node temp;
        currentlevel.push(root);
        while(!currentlevel.empty())
        {
            temp = currentlevel.peek();
            currentlevel.pop();
            if(temp.left!=null)
                nextlevel.push(temp.left);
            if(temp.right!=null)
                nextlevel.push(temp.right);
            if(level%k == 0)
            {
                Node n = temp.left;
                temp.left = temp.right;
                temp.right = n;
            }
            if(currentlevel.empty())
            {
                Stack<Node> t = currentlevel;
                currentlevel = nextlevel;
                nextlevel = t;
                level++;
            }
        }
    }

    public static void InOrderRec(Node root)
    {
        if(root == null)
            return;
        InOrderRec(root.left);
        sout(root.data);
        InOrderRec(root.right);
    }

    public static Node ConstuctTree(int[][] tree)
    {
        Node root = new Node(1);
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        for(int i=0;i<tree.length;i++)
        {
            Node left,right;
            if(tree[i][0]!=-1)
                left = new Node(tree[i][0]);
            else
                left = null;
            if(tree[i][1]!=-1)
                right= new Node(tree[i][1]);
            else
                right = null;

            Node temp = q.remove();
            temp.left = left;
            temp.right = right;

            if(left!=null)
                q.add(left);
            if(right!=null)
                q.add(right);
        }
        return root;
    }


    public static void sout(int info)
    {
        System.out.printf("%d ",info);
    }
}

class Node{
    int data;
    Node left,right;
    Node(int item)
    {
        data = item;
        left = null;
        right = null;
    }
}

Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
vector<int> leftNode, rightNode;
int swapLevel;

void traverse(int node=1){
    if (node == -1) return;
    traverse(leftNode[node]);
    cout << node << " ";
    traverse(rightNode[node]);
    if (node == 1) cout << endl;
}

void swap(int level=1, int node=1) {
	if (node == -1) return;
	if (level % swapLevel == 0) {
		int tmp = leftNode[node];
		leftNode[node] = rightNode[node];
		rightNode[node] = tmp;
	}
	swap(level+1, leftNode[node]);
	swap(level+1, rightNode[node]);
}

int main() {
    int count;    
    cin>>count;
	leftNode.push_back(0);
    rightNode.push_back(0);
    while(count--){
        int L, R;
        cin>>L>>R;
        leftNode.push_back(L);
        rightNode.push_back(R);
    }
    cin>>count;
    while(count--){
		cin >> swapLevel;
		swap();
		traverse();
	}
    return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>


struct node {
    int data;
    struct node *left;
    struct node *right;
};

struct node* create_node(int val){
    if(val == -1){
        return NULL;
    }
    struct node *temp=(struct node*)malloc(sizeof(struct node));
    temp->data=val;
    temp->left=NULL;
    temp->right=NULL;
    return temp; 
}

void inorder(struct node *root){
    if(!root){
        return;
    }    
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int max(int a, int b){
    if(a>b){
        return a;
    } else {
        return b;
    }
}

int height(struct node * root){
    if(!root){
        return 0;
    }
    return(1+max(height(root->left),height(root->right)));
}

void swap_nodes_at_level(struct node *root, int inc, int level, int height){
    struct node *tnode;
    if(!root){
        return;
    }
    if(level > height){
        return;
    }
    if(!(level%inc)){
        tnode=root->left;
        root->left=root->right;
        root->right=tnode;
    }
    swap_nodes_at_level(root->left, inc, level+1, height);
    swap_nodes_at_level(root->right, inc, level+1, height);
}

int tail=0;
int head=0;


void enqueue(struct node **queue, struct node *root){
    
    queue[tail]=root;
    tail++;   
}

struct node* dequeue(struct node **queue){
    
    struct node *temp = queue[head];
    head++;
    return temp;
}

int main() {
    
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    int nodes_count, i, temp, h, tc_num, index, inc, temp1, temp2;
          
    scanf("%d", &nodes_count);
    
  //  printf("%dn", nodes_count);
    
    // int arr[2*nodes_count+1];
    
    struct node *root_perm, *root_temp;
    
    //queue=create_queue(nodes_count);

    struct node *q[nodes_count];
    for(i=0;i<nodes_count;i++){
        q[i]=NULL;
    }    
    
    //building the array
    
    //arr[0]=1;
    
   // for(i=1;i<=2*nodes_count;i++){
     //   scanf("%d",&temp);
      //  arr[i]=temp;
   //   printf("%d ", arr[i]);
   // }
    
    i=0,index=1;
    root_temp=root_perm=create_node(1);
    enqueue(q, root_temp);
    
    while(index<=2*nodes_count) {
       
        //printf("n In Loop : i : %d",i);
        root_temp=dequeue(q);
        //setting up the left child
        scanf("%d", &temp1);
        if(temp1 == -1){
       
        } else {
            root_temp->left=create_node(temp1);
            enqueue(q, root_temp->left);
        }
        //setting up the right child
        scanf("%d", &temp2);
        if(temp2==-1) {
            
        } else {
            root_temp->right=create_node(temp2);
            enqueue(q, root_temp->right);
        }
        index=index+2;
      //  i++;
        
    }
   
    h = height(root_perm);
    
    scanf("%d", &tc_num);
    
    //printf("%d",tc_num);
    //printf("n");
    
    //inorder(root_perm);
    
    while(tc_num){
        scanf("%d",&inc);
        temp=inc;
        //while(temp < height){
        swap_nodes_at_level(root_perm, inc, 1, h);
        //temp=temp + inc;
        //}
        //temp=0;
        inorder(root_perm);
        printf("n");
        tc_num--;
    }  
    
    //Tree is created at this point 
    
    return 0;
}

Problem solution in JavaScript programming.

function toNumber (arr) { return arr.map(function (i) { return Number(i); })}

function nodesAtDepth(root, depth, current) {
    current = current || 1;
    if (depth === current) {
        return [root];
    } else {
        return (
            [].concat(root.left ? nodesAtDepth(root.left, depth, current + 1) : [])
              .concat(root.right ? nodesAtDepth(root.right, depth, current + 1) : []));
    }
}

function inOrderTraversal(root) {
    var out = [];
    if (root.left) out = out.concat(inOrderTraversal(root.left));
    out.push(root.val);
    if (root.right) out = out.concat(inOrderTraversal(root.right));
    return out;
}

function TNode(v, l, r) {
    this.val = v;
    this.right = r || undefined;
    this.left = l || undefined;
} 
    
TNode.prototype.swap = function () {
    tmp = this.right;
    this.right = this.left;
    this.left = tmp;
}

function swap(root, k, max) {
    var d = k, i = 2;
    while (d <= max) {
        nodesAtDepth(root, d, 1).forEach(function (node) { node.swap(); });
        d = i * k;
        i++;
    }
    console.log(inOrderTraversal(root).join(' '));
}

function processData(input) {
    
    var lines = input.split('n').reverse();
    
    var n = Number(lines.pop().split());
    var nodes = new Array(n+1);
    
    var _index, _lr, i, k;
    
    for (i = 0; i < n ; i++) {
        _index = i + 1;
        nodes[_index] = new TNode(_index);
    }
    
    for (i = 0; i < n ; i++) {
        _index = i + 1;
        _lr = toNumber(lines.pop().split(' '));
        if (_lr[0] > -1) nodes[_index].left = nodes[_lr[0]];
        if (_lr[1] > -1) nodes[_index].right = nodes[_lr[1]];
    }
    
    var ops = Number(lines.pop());
    for (var j = 0; j < ops; j++) {
        k = Number(lines.pop()) ;
        swap(nodes[1], k, n - 1);
    }
    
} 

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

coding problems data structure interview prepration kit