Scala implementing binary tree end nodes using option

For a homework assignment I wrote some scala code in which I have the following classes and object used for modeling a binary tree:. My question is about the sumTree function which creates a new tree where the nodes have values equal to the sum of the values of its children plus it's own value.

I find it rather ugly looking and I wonder if there is a better way to do this. If I use recursion which works top-down this would be easier, but I could not come up with such a function. I have to implement the fold function, with a signature as in the code, to calculate sumTree. First of all, I believe and if I may say so, you've done a very good job.

I can suggest a couple of slight changes to your code:. Additionally consider qualifying super class Tree with sealed. This lets compiler emit warnings whenever a following match expression is not exhaustive - in other words doesn't include all possible cases.

Next little improvement is parametrising fold method with Tree fold[Tree].

Because Scala type inferer works through the expression sequentially left-to-right telling it early that we're going to deal with Tree's lets us omit type information when defining function literal which is passed to fold further on.

The recursion you came up with is the only possible direction that lets you traverse the tree and produce a modified copy of the immutable data structure.

Any leaf nodes have to be created first before being added to the root, because individual nodes of the tree are immutable and all objects necessary to construct a node have to be known before the construction: Sign up for our newsletter and get our top new questions delivered to your inbox see an example. Still there is a way to get rid of the node value matching, not only factor it out.

And personally I would prefer it that way. You use match because not every result you get from a recursive fold carries a sum with it. Yes, not every Tree can carry it, Nil has no place for a value, but your fold is not limited to Trees, is it?

GitHub - FireGoblin/goActorBinaryTree: implementing actor based binary tree from scala course in go

Of course the TreePlus is not really needed as we have the canonical product Tuple2 in the standard library. Your solution is probably more efficient certainly uses less stackbut here's a recursive solution, fwiw.

You've probably turned in your homework already, but I think it's still worth pointing out that the way your code and the code in other people's answers looks like is a direct result of how you modeled the binary trees.

If, instead of using an algebraic data type TreeNodeNilyou had gone with a recursive type definition, you wouldn't have had to use pattern matching to decompose your binary trees. Here's my definition of a binary tree:. As you can see there's no need for Node or Nil here the latter is just glorified null anyway aftermarket parts remington 597 you don't want anything like this in your code, do you?

No pattern matching needed anywhere - all because of a nice recursive definition of binary trees. By posting your answer, you agree to the privacy policy and terms of service. By subscribing, you agree to the privacy policy and terms of service. Stack Overflow Questions Developer Jobs Documentation beta Tags Users. Sign up or log in to customize your list. Tour Start here for a quick overview of the site Help Center Detailed answers to any questions you might have Meta Discuss the workings and policies of this site About Us Learn more about Stack Overflow the company Business Learn more about hiring developers or posting ads with us.

Log In Sign Up. Join the Stack Overflow Community. Stack Overflow is a community of 7. Join them; it only takes a minute: Creating sum tree of binary tree scala Ask Question. For a homework assignment I wrote some scala code in which I have the following classes and object used for modeling a binary tree: Tree extends Tree case class Nil extends Tree My question is about the sumTree function which creates a new tree where the nodes have values equal to the sum of scala implementing binary tree end nodes using option values of its children plus it's own value.

I have to implement the fold function, with a signature as in the code, to calculate sumTree I got the feeling this can be implemented in a better way, maybe you have suggestions? Bill the Lizard k I can suggest a couple of slight changes to your code: Tree extends Tree case object Nil extends Tree Tree doesn't need to be a case-class, besides using a case-class irs incentive stock option rules non-leaf node is deprecated because of possible erroneous behaviour of automatically generated methods.

Nil is a singleton and best defined as a case-object instead of case-class. So here is the full code including suggestions: Thanks a lot, especially the last bit of your answer. Vlad This was really helpful, but I don't really understand why commodity futures trading commission forex need for a method val nodeValue: Can anyone explain why it has to be done this way?

Sander, nodeValue abstracts away repetitive code, if you look at the original code in the question it contains two independent match expressions: At this point it might become a bit hard to follow the code, as the authors intent is muddled in detail.

Replacing the repetitive code with the single helper function that has a descriptive name better reflects intent and slices the code into more manageable units.

The great thing about Scala is how easy it is to add a little helper function and limit its scope to the immediate place of application. VladGudim I understand it replaces the match expressions. I'm working on exactly the same exercise by the way. I'm curious why I can't use a sum method I defined earlier to sum all the node values.

Rodrigo De Castro: First program in Scala: porting binary search add/remove from Java

I used that before for the implementation of sumTree without the use of the fold method, but with pattern matching instead. Whenever I try using the sum method right here some nodes appear to be counted twice? As far as I understand the nodeValue function it only return the nodevalues of the 2 nodes directly below the current one? Sander, I'm not aware of this exercise context, so cannot help. Maybe it's worth submitting a separate question with full details and possibly link to this question?

Did you find this question interesting? Try our newsletter Sign up for our newsletter and get our top new questions delivered to your inbox see an example. Please click the link in the confirmation email to activate your subscription.

As Vlad writes, your solution has about the only general shape you can have with such a fold. Tree Now we can fold it like this: Your solution is probably more efficient certainly uses less stackbut here's a recursive solution, fwiw def sum tree: Thanks for your answer, I did something similar in another assignment where I didn't use the fold function.

Dave Griffith both solutions are recursive but will not be optimised by the Scala compiler and will use the same number of stack frames. In Roelio's solution recursion involves alternate calls between fold and the anonymous function passed to fold as the third parameter - another scenario that Scala compiler can't optimise through tail call elimination.

Here's my definition of a binary tree: Option[Tree[A]] As you can see there's no need for Node or Nil here the latter is just glorified null anyway - you don't want anything like this in your code, do you? With such definition, fold is essentially a one-liner: Sign up or log in StackExchange. Sign up using Facebook. Sign up using Email and Password. Post as a guest Name. In it, you'll get: The week's top questions and answers Important community announcements Questions that need answers.

Scala binary tree · GitHub

Stack Overflow works best with JavaScript enabled. MathOverflow Mathematics Cross Validated stats Theoretical Computer Science Physics Chemistry Biology Computer Science Philosophy more 3. Meta Stack Exchange Stack Apps Area 51 Stack Overflow Talent.