You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
I think the datastructure for tree has been defined 'wrong'. sealed trait Tree[+A] case class Leaf[A](value: A) extends Tree[A] case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
The problem with this current definition is it can have different 'size' depending on how you count the tree.
Currently the tree can have node without value. it is purely node. e.g. Branch(Branch(Leaf(2), Branch(Leaf(3), Leaf(3))), Leaf(1))
If you draw it on the paper, it will have 3 'branch' without value, the first one is the root; and it has 3 leaves with values.
So do you count the tree size as 4(only leaves) or 7(leaves and nodes)? or even 5?
using the answer provided in the current master branch ends up with 5.
I think the datastructure for tree has been defined 'wrong'.
sealed trait Tree[+A] case class Leaf[A](value: A) extends Tree[A] case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
The problem with this current definition is it can have different 'size' depending on how you count the tree.
Currently the tree can have node without value. it is purely node. e.g.
Branch(Branch(Leaf(2), Branch(Leaf(3), Leaf(3))), Leaf(1))
If you draw it on the paper, it will have 3 'branch' without value, the first one is the root; and it has 3 leaves with values.
So do you count the tree size as 4(only leaves) or 7(leaves and nodes)? or even 5?
using the answer provided in the current master branch ends up with 5.
Instead, after quick search on the internet, the answer on this stackexchange gives better data structure for the tree https://codereview.stackexchange.com/questions/102470/binary-tree-implementation-in-scala But of course, it does not need to be binary tree (so the 'isValid' part is not needed)
The text was updated successfully, but these errors were encountered: