Some error occured while loading page for you. Please try again.
Sort 9 Discussions, By:
Please Login in order to post a 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.
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.
Thank you for the answer, what do you mean by level traverse order?
If my tree should be like this:
6 7 8
\ / \
9 10 11
And my list looks likes this
I cannot see any level traverse order. For example how do [4, -1], [6, -1] [-1 9] get grouped together on the same branch?
/ / \
/ / \
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]
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
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.
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.
Why test case #2 first swap at both 2 and 4 but second swap at 4 only?
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,...].
- 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
Oh, it's my fault, thank you very much :)
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.
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?
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.
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.
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.
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.
For testcase 2: the lines in the example output seem to be in reverse order.
The example outputs are correct, check the explanations below.
C compiler is not available for this problem.
Please provide the c Or c++ compiler for all problem.
This problem is for Functional programming languages only.
then what about c++ developers
Bu functional programming we mean functional paradigm, not a language which support functions.
Probably you are looking for algo challenges.
No more comments