Algorithm


Problem Name: Data Structures - Swap Nodes [Algo]

Problem Link: https://www.hackerrank.com/challenges/swap-nodes-algo/problem?isFullScreen=true

In this HackerRank in Data Structures - Swap Nodes [Algo] solutions

A binary tree is a tree which is characterized by one of the following properties:

 

  • It can be empty (null).
  • It contains a root node only.
  • It contains a root node with a left subtree, a right subtree, or both. These subtrees are also binary trees.

 

In-order traversal is performed as

 

  1. Traverse the left subtree.
  2. Visit root.
  3. Traverse the right subtree.

 

For this in-order traversal, start from the left child of the root node and keep exploring the left subtree until you reach a leaf. When you reach a leaf, back up to its parent, check for a right child and visit it if there is one. If there is not a child, you've explored its left and right subtrees fully. If there is a right child, traverse its left subtree then its right in the same manner. Keep doing this until you have traversed the entire tree. You will only store the values of a node as you visit when one of the following is true:

 

  • it is the first node visited, the first time visited
  • it is a leaf, should only be visited once
  • all of its subtrees have been explored, should only be visited once while this is true
  • it is the root of the tree, the first time visited

 

Swapping: Swapping subtrees of a node means that if initially node has left subtree L and right subtree R, then after swapping, the left subtree will be R and the right subtree, L.

 

For example, in the following tree, we swap children of node 1.

 

                                Depth
    1               1            [1]
   / \             / \
  2   3     ->    3   2          [2]
   \   \           \   \
    4   5           5   4        [3]

 

In-order traversal of left tree is 2 4 1 3 5 and of right tree is 3 5 1 2 4.

 

Swap operation:

 

We define depth of a node as follows:

 

  • The root node is at depth 1.
  • If the depth of the parent node is d, then the depth of current node will be d+1.

 

Given a tree and an integer, k, in one operation, we need to swap the subtrees of all the nodes at each depth h, where h ∈ [k, 2k, 3k,...]. In other words, if h is a multiple of k, swap the left and right subtrees of that level.

 

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.

 

Function Description

 

Complete the swapNodes function in the editor below. It should return a two-dimensional array where each element is an array of integers representing the node indices of an in-order traversal after a swap operation.

swapNodes has the following parameter(s):
- indexes: an array of integers representing index values of each node[i] , beginning with node[1] the first element, as the root.
- queries: an array of integers, each representing a k value.

Input Format
The first line contains n, number of nodes in the tree.

 

Each of the next n lines contains two integers, a b, where a is the index of left child, and b is the index of right child of ith node.

 

Note: -1 is used to represent a null node.

The next line contains an integer, t, the size of queries

Each of the next t lines contains an integer queries[i], each being a value k.

Output Format
For each k, perform the swap operation and store the indices of your in-order traversal to your result array. After all swap operations have been performed, return your result array for printing.

 

Constraints

  • 1 <= n <= 1024
  • 1 <= t <= 100
  • 1 <= k <= n
  • Either a = -1 or 2 <= a <= n
  • Either b = -1 or 2 <= b <= n
  • The index of a non-null child will always be greater than that of its parent.

Sample Input 0

 

3
2 3
-1 -1
-1 -1
2
1
1

 

Sample Output 0

 

3 1 2
2 1 3

 

Explanation 0

 

As nodes 2 and 3 have no children, swapping will not have any effect on them. We only have to swap the child nodes of the root node.

 

    1   [s]       1    [s]       1   
   / \      ->   / \        ->  / \  
  2   3 [s]     3   2  [s]     2   3

 

Note: [s] indicates that a swap operation is done at this depth.

 

Sample Input 1

 

5
2 3
-1 4
-1 5
-1 -1
-1 -1
1
2

 

Sample Output 1

 

4 2 1 5 3

 

Explanation 1

 

Swapping child nodes of node 2 and 3 we get

 

    1                  1  
   / \                / \ 
  2   3   [s]  ->    2   3
   \   \            /   / 
    4   5          4   5  

 

Sample Input 2

 

11
2 3
4 -1
5 -1
6 -1
7 8
-1 9
-1 -1
10 11
-1 -1
-1 -1
-1 -1
2
2
4

 

Sample Output 2

 

2 9 6 4 1 3 7 5 11 8 10
2 6 9 4 1 3 7 5 10 8 11

 

Explanation 2

Here we perform swap operations at the nodes whose depth is either 2 or 4 for K = 2 and then at nodes whose depth is 4 for K = 4

.

         1                     1                          1             
        / \                   / \                        / \            
       /   \                 /   \                      /   \           
      2     3    [s]        2     3                    2     3          
     /      /                \     \                    \     \         
    /      /                  \     \                    \     \        
   4      5          ->        4     5          ->        4     5       
  /      / \                  /     / \                  /     / \      
 /      /   \                /     /   \                /     /   \     
6      7     8   [s]        6     7     8   [s]        6     7     8
 \          / \            /           / \              \         / \   
  \        /   \          /           /   \              \       /   \  
   9      10   11        9           11   10              9     10   11 

 

 

 

 

 

Code Examples

#1 Code Example with C Programming

Code - 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("%d\n", 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;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - 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;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - 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 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;
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - 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);
});
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - 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('')
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Tree: Huffman Decoding solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved]Is This a Binary Search Tree? solution in Hackerrank - Hacerrank solution C, C++, java,js, Python