# Swap Nodes [Algo]

# Swap Nodes [Algo]

xialin + 15 comments One of the most ambiguous question on HackerRank. I wish I could down vote the problem description.

whoiscris + 5 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.

xialin + 1 comment It's not about difficulty. it's about clarity.

yash_krgupta_ee1 + 1 comment me too facing too dificulty in understanding the problem

avinashk8083 + 1 comment i am also facing dificulty in understanding

epicure + 0 comments me too, one of the less clear problems

mark55 + 1 comment 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.

vucislav + 1 comment 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.lingbo19_tang + 2 comments 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.

jack_yang243 + 1 comment 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).

alaniane + 1 comment 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 / \ 3 2 / \ / \ 10 6 9 17

Is still a binary tree. It's not sorted, but that does not disqualify it as a binary tree.

rachelrotteveel2 + 0 comments 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.

itskshitizsh + 0 comments [deleted]

ypahalajani + 0 comments I got to learn a lot!

rishabh_ags + 0 comments Yes it's as "not ambiguous" as the number of downvotes on you comment :P

rasik210 + 4 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:

- 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; } }`

h670363997 + 1 comment My algorithm is the same as yoursï¼Œbut i did not pass all the test.

dana_w + 0 comments Yeah, same here. I only passed some tests. I wonder what we're doing wrong...

vincentvand + 0 comments 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 :)

kunal_manish1 + 0 comments my algo is similar to yours but i am not able to clear 3 tests cases!

tvichvy + 0 comments 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.

kenji4861 + 1 comment "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..

walkerp07 + 0 comments Thanks.

kimberlyu + 1 comment 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.

garykhong + 0 comments Thanks for explaining the multiples of every depth. The problem description and examples do not make it very clear at all.

juharri3 + 0 comments 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.

acs2010 + 0 comments I totally agree. Could someone please describe the problem for me in English ?

UWUTM8 + 0 comments I was thinking the same thing after 20 minutes!

VINAY_VKK + 0 comments Yes but thank god they gave explanation with examples, if not it would have been even worse than now to understand

NandiChaurasiya + 0 comments I too found this problem as one of better problem where I learned lot of things.

randspence + 0 comments 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.

7heaven + 4 comments 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); } }

manishi_sharma98 + 0 comments [deleted]pc06matt + 0 comments [deleted]pc06matt + 0 comments Wow! Thats what I wanted to learn. I did the same thing with all the basic concepts, because I got tired with so much work in this problem. But your elegant code took it to next level

static void swapSPL(int k){ int btLevels=maxDepth(root); //System.out.print("K="+k+", NumberOfLevels="+btLevels); int j=1; for(int i=k;i { if (node == null) return; if (k == 1)

{ //System.out.print(" Swaping for this "+node.key + " "); Node temp=node.right; node.right= node.left; node.left=temp; return; }

else { swapKDistant(node.left, k - 1); swapKDistant(node.right, k - 1); } }cindysg + 1 comment Agree. building the tree is more difficult/complex than swapping. Would you please share your c/c++ code of building the tree with queue or other method here? thanks!

kunal_manish1 + 1 comment give you email .ill email it to you

cindysg + 1 comment Hi, Kunal,

Thanks. you may contact me on cindygaopan@hotmail.com

thanks,

harindermaheshw1 + 0 comments hey, can you forward me the code too if you have recivied the code over this mail ID: harindermaheshwari@gmail.com

markuhl327 + 0 comments 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..

kamanashisroy + 0 comments I wish someone delete this problem. It does not worth my time.

rajazzam22 + 0 comments 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.

stefanks + 15 comments In python had to change recursion limit to work on the last two test inputs

import sys sys.setrecursionlimit(15000)

carborundum + 2 comments I used a loop with a deque as a stack instead to get around that problem

magoarcano + 1 comment I used a loop with a deque as a queue too but it didn't get around that problem with that solution

reddeadya + 0 comments You can use even the list() and it works. See the "Iterative InOrder traversal" example: here on wiki

martincs14 + 0 comments Interesting... can you explain briefly how you used a deque to get around the problem.

j_b_shteyn + 0 comments Thanks for the tip

jellybeanfiend + 1 comment Amazing! This is exactly what I hoped to find in the comments. Thanks!

shukla1804 + 1 comment what prerequisite i need to solve this question

shshnk28 + 2 comments solve level order traversal first. the logic here is similar.

- try to create a tree from the input.
- get the height of the tree.
- read the next set of input. go to the particular level and swap the nodes.

umerfarooq + 1 comment i'm confused, we have to swap nodes(means that whole node containing its child nodes are also moved form left to right or right to left) or we have to swap nodes data.

vinayb21 + 0 comments We have to swap nodes not their data.

manthan_learner + 1 comment I did the same thing but am getting time out in test cases 6,7,10 and 11. Can any one suggest some thing?

coder08122014 + 0 comments same here bro, i first created a tree then inserted nodes acoordingly on the basis of input then swapped but it is giving timeout in test case 6,7,10,11. please provide me an update as soon as u get it,and ill do the same

bibhash + 0 comments Thank you so much! Would never have figured that out.

Keerthanss + 0 comments Thank you!

mulberrylane + 0 comments Awesome, I finally got every test past! Thanks.

imhktc + 0 comments I never knew there was recursion limit, thanks!!

GeoMatt22 + 0 comments 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.)

ayush199429 + 0 comments Thanks a lot!!

jimmy_valentine + 0 comments 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

andrewpan64 + 0 comments 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

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

prabhjyot28 + 0 comments Thanks buddy! you saved my lot of time.

apoulin + 0 comments [deleted]mehulgala007 + 0 comments Thanks you. This was exactly what I came to look for in the comments section.

asharm36 + 2 comments I usually agree with Hackerrank's difficulty ratings, however I feel given how tedious this problem is, it should be a "Moderate" at least

badonkadonk + 2 comments 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".

alan_davies + 1 comment 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.

vikrambs + 0 comments True.. The problem is all about an array representation of non binary tree.

realq86 + 2 comments Solved the problem but had to. 1. Create node object. 2. Create a breathFirst to read input. 3. Create a depthFirst to change height. 4. Create a Inorder to print.

Took 3 hours total. Is is listed as "Easy?" Is there an easier way than the apporche I did?

ludopulles + 4 comments 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 :).

realq86 + 3 comments Hi, Thanks for the tip. So you mean you just used an array and didn't create a binary tree data structure?

I actually created a tree, loaded it with data swap the subtree, and traverse the tree to print the output.

Sounds like I over engineered! Would you like to exchange solutions?

ludopulles + 15 comments Hmm, well, I used an array but it represents a binary tree, so I would call it a binary tree data structure :P. Here is my solution: http://ideone.com/Fml7Sm You can see, I didn't use a BFS but I iterated over the array. This is possible because a swap won't change the depth of a node, so the order in which you swap nodes doesn't matter.

realq86 + 0 comments You serialized the tree! In this case a good call, since the input is serialized to begin with.

HarryCho + 0 comments great answer!

keyul + 0 comments Thanks for idea of Two different arrays to store left and right node.

raina_venki + 1 comment Hi, your code is not giving any output for this following input...

5

2 2

3 -1

-1 3

-1 -1

-1 -1

2

1

1

ludopulles + 3 comments The tree you give, is not a tree:

- the right child of node 3 is itself
- both the left and right child of node 1 are 2.

So we can assume that this input won't appear as one of the test cases.

raina_venki + 0 comments sorry i didn't get you.... 1 is the root, 1st 2 is left child of 1 and 2nd 2 is the right child of 1,

1st 3 is the left child of 1st 2 and right child of 1st 2 is null,

2nd 3 is the right child of 2nd 2 and left child of 2nd 2 is null,

both children of both 3 will be null.... this is the tree right.......

raina_venki + 1 comment and i don't understand why you mentioned that both left and right child of node 1 are 2.....yeah...i can be right....since it is a binary tree not a binary search tree....and there no such rule that there shouldn't be duplicate nodes....and both the children are greater than their parent....

ludopulles + 1 comment The 4th line of input is

`-1 3`

, which shows the left and right child of node 3. Nodes start from 1. So there is a cycle 3 -> 3. Therefore it is not a tree.raina_venki + 1 comment that fourth line of input are children of the right child of root node right....not the children of 3....

ludopulles + 1 comment Uhm, no... Check the input format. It explains it quite well.

aayush_break + 0 comments [deleted]

gschoen + 2 comments It's a tree but with nodes that have duplicate data.

1 / \ 2 2 / \ 3 3

In this case, swapNodes won't change the nature of the tree.

raina_venki + 0 comments it is not mentioned in the problem.....or in the input conditions........

tvichvy + 0 comments There is no data (well, you could say node's own index is its payload). It's just a bunch of indexes. So the root has node number 2 as a left child and also a right child. And node number three has itself as a right child.

Not a tree. Somebody just doesn't understand the format. Which really isn't surprising given the poor description.

But if anyone wants it blow by blow:

- 5 // there are five nodes
- 2 2 // root (node 1) has node 2 as left child and node 2 as right child
- 3 -1 // node 2 has node 3 as left child
- -1 3 // node 3 has node 3 as right child
- -1 -1 // node 4 has no children
- -1 -1 // node 5 is the same

aj510 + 0 comments Wow, very nice! I did the same as realq86 (created tree data struct and methods). Thank you for sharing your code! Clever :D

Zen_Programmer + 0 comments Thank you!! wonderful code...Helped me when i was stuck tring to figure out the depth!

ypahalajani + 0 comments You used 2 arrays for storing left and right children. Genius! BTW: how do you come with such great logic and how much time does it take, GENERALLY ?

prasanthsri09 + 0 comments Upvote! Upvote! Upvote!

spartacus_arena + 0 comments @ludopulles thanks for your solution.

ravin_dra + 0 comments this is so cool

long0133 + 1 comment Your solution may fail if input numbers are not in increment order. For example,

3

3 -1

2 -1

-1 -1

2

1

1

(while it works when in order:

3

2 -1

3 -1

-1 -1

2

1

1 )

One more example:

5

4 5

2 -1

-1 3

-1 -1

-1 -1

1

1

The problem is because you use the input value as array index.

paucarchris + 0 comments Check your examples again, they're not BST. The first example says node 3 is a child of node 1, yet node 2 is a child of node 2?

Second example works because it's a BST. Third example says node 4 and 5 are children of node 1, node 2 is its own child, node 3 is its own child.

eloyekunle + 0 comments That solution is one of the best for this problem.

smithosagie24 + 0 comments Please, can you explain the depth method?

cindysg + 0 comments fantastic solution! thanks for sharing!

Lherbeur + 0 comments Very good idea!

chued + 0 comments While it is over engineering, your approach seems to be the learning intent of the problem. All 4 steps are outputs from prior problems. It should be a re-create with minor modifications exercise, hence the 'easy'. The wording of the problem, on the other hand...

coder08122014 + 0 comments exactly i also did the same but i guess theres more optimal solution present

SachitMNayak + 0 comments yup! same here !

nikolaijivkov + 0 comments It certainly took a lot of writing, but I think it's easy becouse all of these tasks we had to solve in order to get to this one.

I've certainly learned a lot from this site :)

TheLastOrca + 0 comments Yes, I did not have to construct a tree. I swapped them according to the levels. But struggled with traversing it after swapping.

waitingkuo + 0 comments same here. the algorithm is easy, but its implementation is so hard

pburakov + 0 comments The problem is not hard at all, but very poor description and badly structured input make it a lot harder than it should be. I would suggest some areas for clarification. Is

*i*the line number? Or is it node index? It's actually both, and the right answer is that null node should not be indexed but line numbers go on. It's not immediately clear if*K*is applied to depth or height, because below for some reason letter*h*is used to represent the depth. Use of index in the input and other constrains literally enforce the use of array upon the user.

sarthakgarg + 3 comments This question is by no means an 'Easy' one. It is really time intensive since it needs to be started from scratch. Also, if possible, then please simplify the wording of the question.

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

EdwardSkrod + 1 comment I agree. The wording is very difficult to understand.

harshittest + 0 comments Make it simple to understand.

bennattj + 0 comments 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

m1samuel + 1 comment Once I got through building the tree from the messed up format it was given in, it was actually a pretty straight forward BFS problem. Also, I would like to add that practicing building a graph representation of data given in a messed up format is excellent practice as this is highly likely to occur during an interview. Haven't seen too many python solutions, so here's mine:

class Node: def __init__(self, d): self.data = d def build_tree(indexes): f = lambda x: None if x == -1 else Node(x) children = [list(map(f,x)) for x in indexes] nodes = {n.data: n for n in filter(None, sum(children, []))} nodes[1] = Node(1) for idx, child_pair in enumerate(children): nodes[idx+1].left = child_pair[0] nodes[idx+1].right = child_pair[1] return nodes[1] def inorder(root): stack = [] curr = root while stack or curr: if curr: stack.append(curr) curr = curr.left elif stack: curr = stack.pop() yield curr.data curr = curr.right def swap_nodes(indexes, queries): root = build_tree(indexes) for k in queries: h = 1 q = deque([root]) while q: for _ in range(len(q)): node = q.popleft() if h % k == 0: node.left, node.right = node.right, node.left q += filter(None, (node.left, node.right)) h += 1 yield inorder(root)

pnaraya4 + 1 comment 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?hubrando + 0 comments Yield means that it returns the current state and then continues from where it last stopped when its called.

oguzhanyalcin + 0 comments The worst question I've read....

imaginationsuper + 6 comments Use either Iterative or Recursive method to swap nodes:

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class Node { int data; int depth; Node left, right; Node(int data, int depth){ this.data = data; this.depth = depth; } } public class Solution { public static void swap_nodes(Node root, int K){ /*Queue<Node> nodes = new LinkedList<Node>(); nodes.offer(root); Node cur; while (!nodes.isEmpty()){ cur = nodes.poll(); if (cur.depth%K == 0){ Node tmp = cur.left; cur.left = cur.right; cur.right = tmp; } if (cur.left != null) nodes.offer(cur.left); if (cur.right != null) nodes.offer(cur.right); }*/ if (root != null){ if (root.depth%K == 0){ Node tmp = root.left; root.left = root.right; root.right = tmp; } swap_nodes(root.left, K); swap_nodes(root.right, K); } } public static void inorder_print(Node root){ if (root != null){ inorder_print(root.left); System.out.print(root.data+" "); inorder_print(root.right); } } public static void print_nodes(Node root, int K){ swap_nodes(root, K); inorder_print(root); System.out.println(); } public static void main(String[] args) { /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); Node root = new Node(1, 1); Node cur = root; Queue<Node> nodes = new LinkedList<Node>(); nodes.offer(cur); while (N-->0){ cur = nodes.poll(); int leftData = sc.nextInt(); int rightData = sc.nextInt(); cur.left = (leftData==-1)? null: new Node(leftData, cur.depth+1); cur.right = (rightData==-1)? null: new Node(rightData, cur.depth+1); if (cur.left != null && cur.left.data!= -1) nodes.offer(cur.left); if (cur.right != null && cur.right.data!=-1) nodes.offer(cur.right); } int T = sc.nextInt(); while (T-->0){ int K = sc.nextInt(); print_nodes(root, K); } } }

garyzhang2681 + 0 comments Almost the same as mine!

shubhamv23 + 0 comments [deleted]anupam_1482002 + 0 comments HI @imaginationsuper , Could you please let me know why you are checking if (root.depth%K == 0)?

jashan_bhullar + 0 comments Great Solution ,Thanks

rahulmbw + 0 comments Great Solution

vvbhandare + 0 comments Please provide some explanation, if possible.

RepliCat + 3 comments Using the recursive approach on Python3, failed at Test Case #10 and #11. Turns out the number of nodes exceeded the maximum recursion depth, fixed using

`sys.setrecursionlimit()`

.jnawrocki + 0 comments thank you! was driving me crazy

codeartcz + 0 comments thanks. i spent one hour solving #10 and #11

gongxun_cn + 0 comments TIL.

Sort 410 Discussions, By:

Please Login in order to post a comment