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.
Swap Nodes [Algo]
You are viewing a single comment's thread. Return to all comments →
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 Swapping and for Swap 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.
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.