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.

The part that tripped me up was the 1K, 2K, 3K thing. I kind of glossed over 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..

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 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

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:

void swap(int k,struct node* root,int level)
{
    if(root!=NULL)
    {
        if(level%k == 0)
        {
            t0 = root->left;
            root->left = root->right;
            root->right = t0;
            t0 = NULL;
        }
        swap(k,root->left,level+1);
        cout<<root->data<<' ';
        swap(k,root->right,level+1);
    } 
}

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.

I used a loop with a deque as a stack instead to get around that problem

Thanks for the tip

Amazing! This is exactly what I hoped to find in the comments. Thanks!

Thank you so much! Would never have figured that out.

Thank you!

Awesome, I finally got every test past! Thanks.

I never knew there was recursion limit, thanks!!

Ha! Good trick.

It was fun to work out the in-order traversal using a list-based stack though :)

By the way, a recursion limit of 1200 is sufficient. (1024 is too small for sure.)

Thanks a lot!!

You saved my life bro. I just started coding in python so didn't know that such a thing exists. I was getting this error for past half an hour!Thanks

THANK YOU! I've been trying to memoize the shit out of this problem after passing all of the other test inputs, can't believe all I had to do this whole time was set the recursion limit

Thanks! Saved me a lot of time for needless debugging. Code was (in principle) ok.

Thanks buddy! you saved my lot of time.

I agree. I think building a tree from the input stream, combined with the wording of the question really adds to the complexity of this rather basic problem.

Should be a "Moderate".

It took as much time to get the stdin reading working as it did to do all the previous exercises in this section. The actual 'swap' function was trivial though.

I'm not sure about your breadth-first approach to read input. You should just initialize your array of length n with left and right child.

About the time, if you practice more, you will see that you can solve problems faster and faster! This one took me 10 minutes :).

same here. the algorithm is easy, but its implementation is so hard

It should be easy to append pairs to an array and traverse the tree from there, what was your approach?

I agree. The wording is very difficult to understand.

Well I disagree. I've found many "easy" problems considerably more difficult than this one. I don't really understand the confusion with reading the input.

First, I used a Node class, which held the level for each node (along with the label and left and right children). Then stored the nodes as an array of Nodes (seemed pretty obvious considering the labeling). Finally I used a Map (HashMap) which held a list of nodes at each level.

So reading was pretty straightforward: iterate 0-N to get children. Each time you are setting the children of node[i], further you can set the level of the children by adding one to node[i]'s level. Add the children nodes to the list for that particular level.

Then swapping is incredibly easy: find the list at each level and swap all of those nodes' children. Use previous algorithm (or in my case a much simpler recursive algorithm) to print the new tree in-order.

I know space-wise, that's definitely not the most efficient. But in terms of time-complexity, the most expensive operation is printing the tree.

The one part that I thought about that could have made it more difficult is if they didn't give the nodes "in order" (which I see no where that this was necessary). So for instance, the second node might not have had it's level set when it's children were specified (say because the first node didn't contiain node "2"). I figured if that was the case, you could do some kind of bubble iteration after all of the nodes were parsed. Basically keep iterating through all of the nodes until all of the levels were set

Almost the same as mine!

HI @imaginationsuper , Could you please let me know why you are checking if (root.depth%K == 0)?

Great Solution ,Thanks

Great Solution

Please provide some explanation, if possible.

Why do you yield inorder(root)? Does using yield make it run only once? or does it not initialize stack back to [] but instead continues from where it last stopped?

thank you! was driving me crazy

thanks. i spent one hour solving #10 and #11

TIL.