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.
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?
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Join us
Create a HackerRank account
Be part of a 26 million-strong community of developers
Please signup or login in order to view this challenge
Swap Nodes [Algo]
You are viewing a single comment's thread. Return to all comments →
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?