Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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
- Traverse the left subtree.
- Visit root.
- 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 bed+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;
}
#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;
}
#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;
}
}
#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);
});
#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('')