We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

It's not ambiguous at all. It's not a very deep problem. If you code it clean you won't have any difficulties. Btw, it uses a lot of concepts from the other problems of the Trees section: https://www.hackerrank.com/domains/data-structures/trees.

Yes, it is ambiguous. In one case it says to print the traversal after each swap operation (which for each T there can be more than 1), then it implies that the traversal only needs to be printed T times.

It would not have taken much effort to make this clear.

Actually, a swap operation consists of more swaps, see the definition for Swapping and for Swap operation, so the problem is not ambiguous when it comes to that part.

How can you assume that the root is 1 and another child is 2? And why are you swapping 1 twice? And what's the meaning of the -1 -1, -1 -1. Makes no sense to me.

I think all the information you need is in the problem description. It's just a lot to take in.

The tree with N nodes is rooted at the node with index 1 as described in the Swapping operation section. So the root of the tree is 1.

-1 is used to represent a null node, as described in the Input Format section. For example, the -1s in the second of the N lines mean that the node with index 2 has NULL pointers for both of its children. Similarly, the -1s in the third of the N lines means that the node with index 3 also has NULL pointers for both of its children.

I don't think there's a particular reason why we swap at level 1 twice. The sample inputs are just used to illustrate an example (Sample Input/Output #00 correspond to Test Case #00 in the Explanation section).

Index 1 and the value of the root are not the same. Binary tree root can contain any value. That part of the problem declaration is ambiguous. For example:

5/ \
32/\/ \
106917

Is still a binary tree. It's not sorted, but that does not disqualify it as a binary tree.

The problem says "You are given a tree of n nodes where nodes are indexed from 1..n and it is rooted at 1. " So we can safely assume that the binary tree we will be given for this problem always has a root of 1. I dealt with this by creating a BinaryTree object with a root of 1.

I agree with you specially with the fact that it uses a lot of concepts from the other problems of trees section. I was able to achieve it using a simple algorithm:

Build the tree.

Repeat below steps for every value of k

Perform level order traversal (BFS) of the entire tree.

At each level, if level is a multiple of k then swap the
child of the nodes at that level.

After the level order traversal is done, perform in order traversal (DFS) to print the tree nodes data.

I used below definition of a node while building the tree:

class TreeNode
{
public int Data { get; set; }
public TreeNode LeftChild {get; set;}
public TreeNode RightChild { get; set; }
public int Depth { get; set; }
}

You don't need to build the tree at all. And you can swap and build the answer in one pass. Well, it might depend on the language and datastructure you're given.

"Given a tree and a integer, K, we have to swap the subtrees of all the nodes who are at depth h, where h ∈ [K, 2K, 3K,...].

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 inorder traversal of the current state of the tree."

I agree! This question was ambiguous.
"Given a tree and a integer, K, we have to swap the subtrees of all the nodes who are at depth h, where h ∈ [K, 2K, 3K,...]."
This part was kind of confusing because I associated h with being the height. Also, I didn't quite understand the mathematical notation h ∈ [K, 2K, 3K,...] meant to swap nodes at every depth that was a multiple of K until I looked it up. If that was explained, it would have been a lot less confusing.

I don't think ambiguous is the right word here. Everything you need to do the problem is here, its just not worded very clearly/concisely. This is a good problem, with a terrible description.

The swapping part of the question was actually simple. Getting the input and converting into the tree was actually a bit tedious because of the way the input was given.
Actual swapping could be done just with a simple addition to normal inorder traversal once the tree was built(which required queue, to simplify the process of creating it.)
Here's my swap function. Hope it helps in understanding the problem for anyone who actually found swapping ambiguous:

Wow! Thats what I wanted to learn. I did the same thing with all the basic concepts, because I got tired with so much work in this problem. But your elegant code took it to next level

static void swapSPL(int k){
int btLevels=maxDepth(root);
//System.out.print("K="+k+", NumberOfLevels="+btLevels);
int j=1;
for(int i=k;i
{
if (node == null)
return;
if (k == 1)
{
//System.out.print(" Swaping for this "+node.key + " ");
Node temp=node.right;
node.right= node.left;
node.left=temp;
return;
}
else
{
swapKDistant(node.left, k - 1);
swapKDistant(node.right, k - 1);
}
}

Agree. building the tree is more difficult/complex than swapping. Would you please share your c/c++ code of building the tree with queue or other method here? thanks!

This is one of those questions such that, if I were actually to come across this in industry, I would read it once or twice through and then go talk to the person requesting such an algorithm and discuss it. Even the input set structure is poorly described..

I think it is supposed to be a tutorial for some basic tree concepts as well. Also, some of the ambiguous looking math definitions are actually pretty accurate. Maths always defines it's terms like that, so I thought it was a good practice.

## Swap Nodes [Algo]

You are viewing a single comment's thread. Return to all comments →

One of the most ambiguous question on HackerRank. I wish I could down vote the problem description.

It's not ambiguous at all. It's not a very deep problem. If you code it clean you won't have any difficulties. Btw, it uses a lot of concepts from the other problems of the Trees section: https://www.hackerrank.com/domains/data-structures/trees.

It's not about difficulty. it's about clarity.

me too facing too dificulty in understanding the problem

i am also facing dificulty in understanding

me too, one of the less clear problems

Yes, it is ambiguous. In one case it says to print the traversal after each swap operation (which for each T there can be more than 1), then it implies that the traversal only needs to be printed T times.

It would not have taken much effort to make this clear.

Actually, a swap operation consists of more swaps, see the definition for

Swappingand forSwap operation, so the problem is not ambiguous when it comes to that part.Input is somehow ambiguous, for example

3

2 3

-1 -1

-1 -1

2

1

1

How can you assume that the root is 1 and another child is 2? And why are you swapping 1 twice? And what's the meaning of the -1 -1, -1 -1. Makes no sense to me.

I think all the information you need is in the problem description. It's just a lot to take in.

The tree with N nodes is rooted at the node with index 1 as described in the Swapping operation section. So the root of the tree is 1.

-1 is used to represent a null node, as described in the Input Format section. For example, the -1s in the second of the N lines mean that the node with index 2 has NULL pointers for both of its children. Similarly, the -1s in the third of the N lines means that the node with index 3 also has NULL pointers for both of its children.

I don't think there's a particular reason why we swap at level 1 twice. The sample inputs are just used to illustrate an example (Sample Input/Output #00 correspond to Test Case #00 in the Explanation section).

Index 1 and the value of the root are not the same. Binary tree root can contain any value. That part of the problem declaration is ambiguous. For example:

Is still a binary tree. It's not sorted, but that does not disqualify it as a binary tree.

The problem says "You are given a tree of n nodes where nodes are indexed from 1..n and it is rooted at 1. " So we can safely assume that the binary tree we will be given for this problem always has a root of 1. I dealt with this by creating a BinaryTree object with a root of 1.

What does rooted at 1 mean ? It is ambiguous. Rooted at index 1 or the root element is 1 ?

I got to learn a lot!

Yes it's as "not ambiguous" as the number of downvotes on you comment :P

I agree with you specially with the fact that it uses a lot of concepts from the other problems of trees section. I was able to achieve it using a simple algorithm:

Repeat below steps for every value of k

child of the nodes at that level.

I used below definition of a node while building the tree:

My algorithm is the same as yours，but i did not pass all the test.

Yeah, same here. I only passed some tests. I wonder what we're doing wrong...

Thank you for this reply,

I spent like half an hour debugging with custom inputs only to find out I missed the part where you needed to swap at every depth multiple of k.

After that, my first algorithm was indeed correct :)

my algo is similar to yours but i am not able to clear 3 tests cases!

You don't need to build the tree at all. And you can swap and build the answer in one pass. Well, it might depend on the language and datastructure you're given.

The part that tripped me up was the 1K, 2K, 3K thing. I kind of glossed over that.

Me too .. crazy..

Same here

It took me lot of time to figure out that !

"Given a tree and a integer, K, we have to swap the subtrees of all the nodes who are at depth h, where h ∈ [K, 2K, 3K,...].

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 inorder traversal of the current state of the tree."

Definitely had to read over it 3 times..

Thanks.

I agree! This question was ambiguous. "Given a tree and a integer, K, we have to swap the subtrees of all the nodes who are at depth h, where h ∈ [K, 2K, 3K,...]." This part was kind of confusing because I associated h with being the height. Also, I didn't quite understand the mathematical notation h ∈ [K, 2K, 3K,...] meant to swap nodes at every depth that was a multiple of K until I looked it up. If that was explained, it would have been a lot less confusing.

Thanks for explaining the multiples of every depth. The problem description and examples do not make it very clear at all.

I didn't find it as much ambiguous as convoluted. I mean the code to load the tree was more complex than the in order printing or the swapping.

I totally agree. Could someone please describe the problem for me in English ?

after looking at ur comment i thought its really ambiguous but it takes intellect to understand question too. its not ambiguous

Intellect needed for understanding someone else`s communication. The question is outrightly ambiguous.

I was thinking the same thing after 20 minutes!

Yes but thank god they gave explanation with examples, if not it would have been even worse than now to understand

I too found this problem as one of better problem where I learned lot of things.

I don't think ambiguous is the right word here. Everything you need to do the problem is here, its just not worded very clearly/concisely. This is a good problem, with a terrible description.

The swapping part of the question was actually simple. Getting the input and converting into the tree was actually a bit tedious because of the way the input was given. Actual swapping could be done just with a simple addition to normal inorder traversal once the tree was built(which required queue, to simplify the process of creating it.) Here's my swap function. Hope it helps in understanding the problem for anyone who actually found swapping ambiguous:

Wow! Thats what I wanted to learn. I did the same thing with all the basic concepts, because I got tired with so much work in this problem. But your elegant code took it to next level

static void swapSPL(int k){ int btLevels=maxDepth(root); //System.out.print("K="+k+", NumberOfLevels="+btLevels); int j=1; for(int i=k;i { if (node == null) return; if (k == 1)

{ //System.out.print(" Swaping for this "+node.key + " "); Node temp=node.right; node.right= node.left; node.left=temp; return; }

else { swapKDistant(node.left, k - 1); swapKDistant(node.right, k - 1); } }

Agree. building the tree is more difficult/complex than swapping. Would you please share your c/c++ code of building the tree with queue or other method here? thanks!

give you email .ill email it to you

Hi, Kunal,

Thanks. you may contact me on cindygaopan@hotmail.com

thanks,

hey, can you forward me the code too if you have recivied the code over this mail ID: harindermaheshwari@gmail.com

This is one of those questions such that, if I were actually to come across this in industry, I would read it once or twice through and then go talk to the person requesting such an algorithm and discuss it. Even the input set structure is poorly described..

I wish someone delete this problem. It does not worth my time.

I think it is supposed to be a tutorial for some basic tree concepts as well. Also, some of the ambiguous looking math definitions are actually pretty accurate. Maths always defines it's terms like that, so I thought it was a good practice.