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.
In the first part it says that the input is an array, and then it shows something that looks like a multi-dimensional array as an input sample. So which is it? An array or a multi-dimensional array?
If you test print the indexes 2 D array, you can see that it will print exactly what has been given as input. However, my doubt is whether 1 is the root node in every case because the description hasn't accepted 1 in input but in the explanation they have kept root node=1.
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.
Here it is in java:
int numberOfNodes = indexes.length;
int numOfQueries= queries.length;
int[][] result =new int[numOfQueries][numberOfNodes];
Node root = new Node(1,1);
Node curr = root;
Queue<Node> nodes = new LinkedList<>();
nodes.offer(curr);
//tree creation
int N = 0;
while (N<numberOfNodes)
{
curr =nodes.poll();
int leftNode = indexes[N][0];
int rightNode = indexes[N][1];
curr.left = leftNode == -1?null:new Node(leftNode,curr.depth+1);
curr.right = rightNode == -1?null:new Node(rightNode,curr.depth+1);
//Now we are going to add the nodes for next iteration to create node
if (curr.left!=null && curr.left.data != -1)
nodes.offer(curr.left);
if(curr.right!=null && curr.right.data != -1)
nodes.offer(curr.right);
N++;
}//loop over
}
Can you tell me how do you know which depth you are in?
When you are making the tree you can set the data as the index and the left and right as well but how do you set the depth?
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
Almost had a seizure while going through the description..
hahaha, agreed. I came to the discussion session to try and understand it
here is problem solution in Python java C++ and C programming language. https://solution.programmingoneonone.com/2020/07/hackerrank-swap-nodes-algo-solution.html
Agree. It is unnecessarily wordy.
In the first part it says that the input is an array, and then it shows something that looks like a multi-dimensional array as an input sample. So which is it? An array or a multi-dimensional array?
If you test print the indexes 2 D array, you can see that it will print exactly what has been given as input. However, my doubt is whether 1 is the root node in every case because the description hasn't accepted 1 in input but in the explanation they have kept root node=1.
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.
What does rooted at 1 mean ? It is ambiguous. Rooted at index 1 or the root element is 1 ?
yes. It means the tree has a root node with value '1'.
Binary search tree is sorted not the Binray tree
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...
you're probably missing the bit where if k=2, then you have to swap children at depth =2, depth =4, depth=6 and so on
It was after i passed 2 out of 3 test that i re-read the problem definition and understood this.
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.
can you tell the algo for tree creation. I'm getting an issue in that
Excellent idea of using Queue to track Nodes. Helped me solve this problems correctly.
Can you tell me how do you know which depth you are in? When you are making the tree you can set the data as the index and the left and right as well but how do you set the depth?