# Tree manager

# Tree manager

martin_vojtek + 0 comments The condition "A single node will never have more than children." is not true for test case no. 15

Giulio + 2 comments I have solved this problem but I have cheated :-) 'cause I have used a mutable data structure (in Scala).

To solve this problem in a real "functional way" I should have used immutable data structures. This means that every time I had to change something (change value, add, delete) I should have copied/created an entire new tree with only "that" change. Well, I thought about this for a while but I found this way to approach the problem quite overwhelming. Could anybody show me how to solve this problem with immutable data structures? How do you handle the add/delete/change operations?

paolo_veronelli + 2 comments I suggest have a look here: https://en.wikipedia.org/wiki/Zipper_(data_structure)

Have fun

Giulio + 1 comment Thanks!

paolo_veronelli + 0 comments I've finished 5 minutes ago. It took some patience

sherub_thakur + 0 comments Thanks. Didn't know about zippers.

Ido_Schwartzman + 0 comments A possible approach (which I took) is to treat the entire tree as one big data structure, with a collection of nodes, and various representations of the links between them (i.e. think Graph represented as an adjancy list). You can then expose a trait called Tree, which is in fact just a front for the tree and a specific node in it (i.e. the tree and a node id). Each operation on the node is performed "behind the scenes" as an operation on the entire tree, and then return a new Tree and node. Then again I supposed that's just another way of describing the zipper principle, just implemented in an object-oriented way.

alexr007 + 0 comments task can be solved without zipper and everything is immutable just put the tree and navigation into two different structures

final case class Node(value: Int, children: Vector[Node] = Vector.empty) final case class PathNode(link: Node, pos: Int, parent: Option[Node])

di98jgu + 0 comments Learning something new is why I like this place. I did not know about zipper trees.

But this was a very difficult task in the wrong I my mind. Solving the problem was the easy part. Geting it to pass within the allowed time frame was an entire different story.

If you try to solve this task with erlang and you have issues with timeout, try search for

"Erlang: Read from an input stream in a efficient way"

Using module string will not work, use binaries. I also had to write my own split line method for the operations.

Good luck.

Eberhofer + 0 comments Thanks for all the pointers to the Zipper. That helped a lot. Took me a while to debug and get all the details right but that was fun!

Sort 6 Discussions, By:

Please Login in order to post a comment