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.

I'll divide the problem into 3 parts:

- Building the tree
- Swapping
- Printing results (in-order traversal)

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

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

- 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`

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

- 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`

- 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)); }`

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; }`

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.

Hi, I'm Erik, an engineer from Barcelona. If you like the post or have any comments, say hi.