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
 / \ / \

2. 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 

3. 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
   / \   / \

4. 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

11. 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][0];
    let right = indexes[i][1];
    
    // Getting current depth of the tree
    let depth = tree[i].depth;
    
    // Adding the new nodes to tree
    addNode(left,  depth + 1);
    addNode(right, depth + 1);

    // 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[0] = {value: '1', depth: 1, left: '2',right: '3'}
tree[1] = {value: '2', depth: 2, left: -1, right: -1}
tree[2] = {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.