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.
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?
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.
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....
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.
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
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...
Swap Nodes [Algo]
You are viewing a single comment's thread. Return to all 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?
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 :).
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?
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.
You serialized the tree! In this case a good call, since the input is serialized to begin with.
great answer!
Thanks for idea of Two different arrays to store left and right node.
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
The tree you give, is not a tree:
So we can assume that this input won't appear as one of the test cases.
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.......
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....
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.that fourth line of input are children of the right child of root node right....not the children of 3....
Uhm, no... Check the input format. It explains it quite well.
It's a tree but with nodes that have duplicate data.
1 / \ 2 2 / \ 3 3In this case, swapNodes won't change the nature of the tree.
it is not mentioned in the problem.....or in the input conditions........
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:
Wow, very nice! I did the same as realq86 (created tree data struct and methods). Thank you for sharing your code! Clever :D
Thank you!! wonderful code...Helped me when i was stuck tring to figure out the depth!
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 ?
Upvote! Upvote! Upvote!
@ludopulles thanks for your solution.
this is so cool
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.
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.
That solution is one of the best for this problem.
Please, can you explain the depth method?
fantastic solution! thanks for sharing!
Very good idea!
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...
exactly i also did the same but i guess theres more optimal solution present
yup! same here !
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 :)
Yes, I did not have to construct a tree. I swapped them according to the levels. But struggled with traversing it after swapping.
same here. the algorithm is easy, but its implementation is so hard