Swap Nodes [Algo] HackerRank Solution

Swap Nodes [Algo] HackerRank Solution
Source : https://www.hackerrank.com/challenges/swap-nodes-algo

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 , beginning with , the first element, as the root.
- queries: an array of integers, each representing a 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 i^th node.

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

The next line contains an integer, t, the size of .
Each of the next t lines contains an integer , each being a value .

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

• Either or
• Either or
• The index of a non-null child will always be greater than that of its parent.

Sample Input 0

32 3-1 -1-1 -1211

Sample Output 0

3 1 22 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

52 3-1 4-1 5-1 -1-1 -112

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

112 34 -15 -16 -17 8-1 9-1 -110 11-1 -1-1 -1-1 -1224

Sample Output 2

2 9 6 4 1 3 7 5 11 8 102 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 and then at nodes whose depth is 4 for .

         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 

Source : https://www.hackerrank.com/challenges/swap-nodes-algo

Solution

	// Karthikalapati.blogspot.com
	import java.util.Scanner;
	// Main trick: Repesent our tree as a 1-D array
	public class Solution {
	public static void main(String[] args) {
	/* Create tree */
	Scanner scan = new Scanner(System.in);
	int N = scan.nextInt();
	Pair [] array = new Pair[N+1]; // represents our tree
	for (int i = 1; i <= N; i++) {
	array[i] = new Pair(scan.nextInt(), scan.nextInt());
	}
	/* Perform swaps and print inorder traversals */
	int T = scan.nextInt();
	while (T-- > 0) {
	int K = scan.nextInt();
	swap(array, K, N);
	inorderTraverse(array, 1);
	System.out.println();
	}
	scan.close();
	}
	private static void swap(Pair [] array, int K, int maxDepth) {
	for (int h = K; h <= maxDepth; h += K) {
	swap(array, h, 1, 1);
	}
	}
	private static void swap(Pair [] array, int depthToSwap, int currIndex, int currDepth) {
	if (currIndex < 1) {
	return;
	}
	Pair p = array[currIndex];
	if (currDepth == depthToSwap) {
	p.swapSubtrees();
	} else {
	swap(array, depthToSwap, p.left, currDepth + 1);
	swap(array, depthToSwap, p.right, currDepth + 1);
	}
	}
	private static void inorderTraverse(Pair [] array, int index) {
	if (index != -1) {
	inorderTraverse(array, array[index].left);
	System.out.print(index + " ");
	inorderTraverse(array, array[index].right);
	}
	}
	}
	class Pair {
	int left;
	int right;
	public Pair(int left, int right) {
	this.left = left;
	this.right = right;
	}
	public void swapSubtrees() {
	int temp = left;
	left = right;
	right = temp;
	}
	}