# Swap Nodes problem from HackerRank using JavaScript

I've been struggling with this problem from HackerRank for the last 2 days. I've learned a lot, but there are some guidelines I would like to write for my future self in case I do this problem again.

## Understanding the problem

I'll divide the problem into 3 parts:

1. Building the tree
2. Swapping
3. Printing results (in-order traversal)

## Building the tree

The first thing you need to understand is how to draw a tree given a certain input.

1. Step
```terminal```11
2 3        <-------- You are here
4 -1
5 -1
6 -1
7 8
-1 9
-1 -1
10 11
-1 -1
-1 -1
-1 -1
2
2
4
``````

Drawing the first two children:

```terminal```    1
/ \
2   3
/ \ / \
``````
1. Step
```terminal```11
2 3
4 -1       <-------- You are here
5 -1
6 -1
7 8
-1 9
-1 -1
10 11
-1 -1
-1 -1
-1 -1
2
2
4
``````

Drawing the next two children:

```terminal```         1
/ \
2     3
/ \   / \
4  -1
``````
1. Step
```terminal```11
2 3
4 -1
5 -1       <-------- You are here
6 -1
7 8
-1 9
-1 -1
10 11
-1 -1
-1 -1
-1 -1
2
2
4
``````

Drawing the next two children:

```terminal```         1
/ \
2     3
/ \   / \
4  -1 5  -1
/ \   / \
``````
1. Step
```terminal```11
2 3
4 -1
5 -1
6 -1       <-------- You are here
7 8
-1 9
-1 -1
10 11
-1 -1
-1 -1
-1 -1
2
2
4
``````

Drawing the next two children:

```terminal```         1
/ \
2     3
/ \   / \
4  -1 5  -1
/ \   / \
6  -1
``````
1. Step

Eventually, if you keep reading each line, you'll obtain:

```terminal```               1                                                  1
/ \                                                / \
/   \                                              /   \
2     3                                            2     3
/ \   / \                                          /     /
/   \ /   \                                        /     /
4   -1 5   -1                                      4      5
/ \    /  \                                        /      / \
/   \  /    \                                      /      /   \
6    -1 7     8                 =====>             6      7     8
/ \     / \   / \              Delete -1             \          / \
/   \   /   \ /   \                                    \        /   \
-1   9  -1  -1 10   11                                   9      10   11
/ \        / \  / \
/   \      /   \/   \
-1   -1     -1  -1-1  -1
``````

Only nodes that are different from -1 have children. Thus, you can delete -1 nodes.

At this point, you know how to draw the tree, now let's translate this into code.

```javascript```const Node = (value, depth) => ({value: value, depth: depth});

// Node 1  -> value: 1, depth: 1
// Node 6  -> value: 6, depth: 4
// Node 10 -> value: 10, depth: 5
``````

Now let's build the tree:

```javascript```let tree = [Node(1, 1)];

for(let i = 0; i < indexes.length; i ++){

// Reading left & right values
let left  = indexes[i];
let right = indexes[i];

// Getting current depth of the tree
let depth = tree[i].depth;

// Adding the new nodes to tree

// Assigning new children to current node
tree[i].left  = left;
tree[i].right = right;

}
``````

Defining `addNode(value, depth)` function:

```javascript```const addNode = (value, depth) => {

if(value !== -1) tree.push(Node(value, depth));

}
``````

## Swapping

At this point, we need to change from left to right the children of depth `d` and multiples of `d`.

```javascript```
const swap = (t, d) => {

let tree = [...t];

for(let i = 0; i < tree.length; i ++){

if(tree[i].depth % d === 0){
[tree[i].left, tree[i].right] = [tree[i].right, tree[i].left];
}

}

return tree;

}
``````

## Printing results (in-order traversal)

To understand how in-order traversal works, it's useful to take a look at the following diagram: To get the components in-order traversal, you need to follow the yellow points:

A -> B -> C -> D -> E -> F -> G -> H -> I

So, how to transalte this into code? Let's begin with a simple example:

```terminal```                                1
/ \
2   3
Tree
======================================================
tree = {value: '1', depth: 1, left: '2',right: '3'}
tree = {value: '2', depth: 2, left: -1, right: -1}
tree = {value: '3', depth: 2, left: -1, right: -1}
``````

With a three node tree, the result would be: 2 -> 1 -> 3. What are we doing here?

```javascript```// 1. Print left children  -> print(2)
// 2. Print own value      -> print(1)
// 3. Print right children -> print(3)
const inOrderTraversal = (node, tree) => {

let nextLeftNode  = tree[node - 1].left;
let nextRightNode = tree[node - 1].right;

// 1. Print left children
if(nextLeftNode !== -1)
inOrderTraversal(nextLeftNode, tree);

// 2. Print own value
console.log(node);

// 3. Print right children
if(nextRightNode !== -1)
inOrderTraversal(nextRightNode, tree);

}
``````

This example works for larger trees as well. If you execute `inOrderTraversal(1, tree)` you'll loop through the whole tree and print all the nodes in-order traversal.

You can combine the three parts of the article to create your own solution.

I hope this explanation helps to clarify one of the richest problems in HackerRank. I encourage you to hack your own solution, you'll learn a lot. This problem is a gold mine. Hi, I'm Erik, an engineer from Barcelona. If you like the post or have any comments, say hi.