# Swap Nodes

# Swap Nodes

dagda1 + 1 comment I think building the tree is not the problem, I find the input very unintuitive.

No expanation is given as to how I apply a pair to a particular node.

It almost looks like it is alternating.

If I understood the input format better, I can build the tree.

cyukangAsked to answer + 1 comment the pair means index of a node's left child and right child, from the pair list we can build the tree, pair list appears in level traverse order.

dagda1 + 1 comment Thank you for the answer, what do you mean by level traverse order?

If my tree should be like this:

`1 / \ 2 3 / / 4 5 / / / /\ 6 7 8 \ / \ 9 10 11`

And my list looks likes this '( [2 3] [4 -1] [5 -1] [6 -1] [7 8] [-1 9] [-1 -1] [10 11] [-1 -1] [-1 -1] [-1 -1] )

I cannot see any level traverse order. For example how do [4, -1], [6, -1] [-1 9] get grouped together on the same branch?

cyukang + 0 comments `1 / \ 2 3 / / 4 5 / / \ / / \ 6 7 8 \ / \ 9 10 11`

from the list, [2, 3] means 1's left child is 2 and right child is 3, [4, -1] means 2's left child is 4, right child is null, [5, -1] means 3's left child is 5, right child is null, etc. leaf is represented as [-1, -1]

hololeap + 0 comments In Haskell, you can get the correct order of traversal for printing by setting up a Foldable instance in the correct way and then using the

`toList`

function. (If you define`foldMap`

instead of`foldr`

, it is much easier to get the order correct.) In my solution, it looks like this:import Data.Foldable (toList) import Data.List (intercalate) import Data.Monoid ((<>)) data Tree a = Tree (Tree a) a (Tree a) | Empty instance Foldable Tree where foldMap _ Empty = mempty foldMap f (Tree l a r) = foldMap f l <> f a <> foldMap f r printTree :: Show a => Tree a -> String printTree = intercalate " " . fmap show . toList

bernardosulzbach + 0 comments Don't do what I did!

I made a lot of cognitive effort into numbering the tree by BFS to get the nodes' numbers right. The numbers from the input are the correct ones for the nodes, the input does not jump back or does anything funny to screw you, it is VERY well behaved.

AlecN + 0 comments Hint: don't perform actual subtree swaps, just collect queries and take them into account while traversing tree. I've implemented this in Erlang, works very well.

madooc + 1 comment Why test case #2 first swap at both 2 and 4 but second swap at 4 only?

brem777Asked to answer + 1 comment The swap operation says: 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,...].

So - swap 2 will swap levels 2, 4, 6, 8, etc - swap 4 will swap levels 4, 8, 12,

So, in this example, since the tree height is 4, we should have : - swap 2 -> swaps 2 and 4 - swap 4 -> swaps 4

madooc + 0 comments Oh, it's my fault, thank you very much :)

kobek + 0 comments Is there a way to discuss submissions test cases? I would like to talk about them ( one in particular ) because I have problems with doing the task by hand and would like to find mistake which I make. This 'cost' some hackos so I don't want to spoil it.

dagda1 + 1 comment My understanding of inorder traversal would print the lowest left node value first but according to the output, it is the highest left node.

Why is this?

cyukangAsked to answer + 1 comment your understanding is not complete. for case#2, why shoud 2 comes out first, because it's left subtree is empty. the lowest node is on right subtree, should comes out latter than 2.

dagda1 + 2 comments according to the sample output for 002 it is:

2 9 6 4 1 3 7 5 11 8 10

But the bottom of the left branch is 9. I don't uderstand why 2 is printed first.

cyukang + 0 comments `2 \ 4 / 6 / 9`

for this subtree, inorder traverse, you think 9 comes out first? you may pick up a data-structure book, implement the inorder traverse according the book, then contruct this test case, and have a carefully study according the output.

hololeap + 0 comments The order is: 1. Recurse over the left subtree 2. Print the value of the node 3. Recurse over the right subtree

When looking at node 2, since the left subtree at node 2 is empty, step 1 at this node does nothing and so it goes directly to step 2.

Node 9 is actually at the bottom of the RIGHT branch from the perspective of node 2, so 2 gets printed before 9.

quick_dudley + 1 comment For testcase 2: the lines in the example output seem to be in reverse order.

Shafaet + 0 comments The example outputs are correct, check the explanations below.

sundeepmalik_cse + 1 comment C compiler is not available for this problem. Please provide the c Or c++ compiler for all problem.

dheerajHackerRank Admin + 1 comment This problem is for Functional programming languages only.

abhisheknita06 + 1 comment then what about c++ developers

abhiranjanChallenge Author + 0 comments Bu functional programming we mean functional paradigm, not a language which support functions.

Probably you are looking for algo challenges.

No more comments

Sort 9 Discussions, By:

Please Login in order to post a comment