#getting-started
Title
# getting-started
t

thhh

04/06/2021, 1:10 PM
Help me understand the logic why the code is not returning
``false``
boolean here at once. Details in thread
The code could might feel huge, but my only doubt is in the function
``find()``
inside the if statement
``root == null``
See if
``root == null``
is true, then the
``find``
function must return
``false``
right? But what happens according to debugging is:
``Only should print once BUT it print multiple times (!?) --> null``
``Only should print once BUT it print multiple times (!?) --> null``
``Only should print once and it prints one time only as expected!``
``result true``
The important part in the above println logs is
``Only should print once BUT it print multiple times (!?) --> null``
is
``root == null``
is true and we are entering the
``if``
block, so the function
``find()``
at once MUST return
``true``
and exit right? But what happens it, the code is seemingly ignoring that and not returning
``false``
and instead it's keep on executing!! and here is where I am confused! Code below:
``class TwoSumIV {``
`class TreeNode(var `val`: Int = 0) {`
``var left: TreeNode? = null``
``var right: TreeNode? = null``
``}``
``fun findTarget(root: TreeNode?, k: Int): Boolean {``
``val set: MutableSet<Int?> = HashSet<Int?>()``
``return find(root, k, set)``
``}``
``fun find(root: TreeNode?, k: Int, set: MutableSet<Int?>): Boolean {``
``if (root == null) {``
`println("Only should print once BUT it print multiple times (!?) --> \${root?.
``val``
}")`
``return false``
`} else if (set.contains(k - root.
``val``
)) {`
``println("Only should print once and it prints one time only as expected!")``
``return true``
``}``
``val``
)`
``return find(root.left, k, set) || find(root.right, k, set)``
``}``
``}``
``fun main() {``
``val root = TwoSumIV.TreeNode(5)``
``root.left = TwoSumIV.TreeNode(3)``
``root.right = TwoSumIV.TreeNode(6)``
``println(root)``
``val twoSumIV = TwoSumIV()``
``val result = twoSumIV.findTarget(root, 9)``
``println("result \$result")``
``}``
h

04/06/2021, 1:29 PM
Playgrounds are much more fun to use 😉 https://pl.kotl.in/eCNu_QZb8 I simply added a print statement to the case which returns ‘true’ and you can see what happens: k = 9, val = 6 set = [3,5] You check if
``k - val``
is in the set.
``9 - 6 = 3``
is indeed present, so it returns
``true``
.
t

tddmonkey

04/06/2021, 1:31 PM
Why do you think it should only be printed once? By my reckoning it should be printed twice
h

04/06/2021, 1:31 PM
Also,
``println``
that you expect to only be executed once, will in fact be executed as many times as many leaves you visit before terminating
m

Michael Böiers

04/06/2021, 8:48 PM
`var `val`` … seriously?
🤣 2
t

therealbluepandabear

04/07/2021, 2:31 AM
Change 'val' to 'value'; seriously, it's beyond bizarre.
m

Michael Böiers

04/07/2021, 6:55 AM
Here’s a clean version of the code. Just for fun 🙂 https://pl.kotl.in/J-JC4bMLL
Copy code
``````data class Node(val value: Int = 0, val left: Node? = null, val right: Node? = null)

class TwoSumIV {
fun findTarget(n: Node, k: Int) = find(n, k, HashSet())

private fun find(n: Node?, k: Int, set: MutableSet<Int>): Boolean = when {
n == null -> false
set.contains(k - n.value) -> true
else -> {
with (n) {
sequenceOf(left, right).any { find(it, k, set) }
}
}
}
}

fun main() {
Node(5, left = Node(3), right = Node(6)).let {
println("result \${TwoSumIV().findTarget(it, k = 9)}")
}
}``````
t

tddmonkey

04/07/2021, 6:59 AM
No sealed class hierarchy for the Nodes? 😄
And tbh, I find (ha!) your
``find``
method to be much harder to read than the original
m

Michael Böiers

04/07/2021, 6:59 AM
I misread that - thought you meant the
``with``
, which was a little over the top.
t

tddmonkey

04/07/2021, 7:10 AM
I do now wonder if a sealed class hierarchy (Node, NoNode, SomeNode) might clean that up
m

Michael Böiers

04/07/2021, 7:20 AM
What do you mean - the nullable children?
Here’s a more concise version using an extension function. Still using
``with``
just because I can’t use a block of code in the boolean expression directly.
Copy code
``````data class Node(val value: Int = 0, val left: Node? = null, val right: Node? = null) {
val children = sequenceOf(left, right)
}

class TwoSumIV {
fun findTarget(n: Node, k: Int) = n.find(k, HashSet())

private fun Node.find(k: Int, set: MutableSet<Int>): Boolean =
set.contains(k - value) || with (children) {
filterNotNull().any { it.find(k, set) }
}
}

fun main() {
Node(5, left = Node(3), right = Node(6)).let {
println(it)
println("result \${TwoSumIV().findTarget(it, k = 9)}")
}
}``````
Damn, refactoring is like a rabbit hole. 😉
Copy code
``````data class Node(val value: Int = 0, val left: Node? = null, val right: Node? = null) {
val children = listOfNotNull(left, right)
}

class TwoSumIV {
fun findTarget(n: Node, k: Int) = n.find(k, HashSet())

private fun Node.find(k: Int, set: MutableSet<Int>): Boolean =
k - value in set || with (children) {
set += value
any { it.find(k, set) }
}
}

fun main() {
Node(5, left = Node(3), right = Node(6)).let {
println(it)
println("result \${TwoSumIV().findTarget(it, k = 9)}")
}
}``````
t

tddmonkey

04/07/2021, 8:32 AM
Copy code
``````sealed class TreeNode(val value: Int) {
abstract fun find(k: Int): Boolean
}

class LeafNode(value: Int): TreeNode(value) {
override fun find(k: Int): Boolean {
return value == k
}
}

class BranchNode(value: Int, val left: TreeNode, val right: TreeNode): TreeNode(value) {
override fun find(k: Int): Boolean {
if (value == k) {
return true
}
return left.find(k) || right.find(k)
}
}

class TwoSumIV {
fun findTarget(root: TreeNode, k: Int): Boolean {
return root.find(k)
}
}
fun main() {
val root = BranchNode(5, left = LeafNode(3), right = LeafNode(6))
println(root)
val twoSumIV = TwoSumIV()
println("Tree has 6 -> \${twoSumIV.findTarget(root, 6)}")
println("Tree has 9 -> \${twoSumIV.findTarget(root, 9)}")
}``````
m

Michael Böiers

04/07/2021, 8:42 AM
Isn’t this more concise?
Copy code
``````data class Node(val value: Int, val left: Node? = null, val right: Node? = null) {
private val children = listOfNotNull(left, right)
fun find(k: Int): Boolean = value == k || children.any { it.find(k) }
}

fun leafOf(value: Int) = Node(value)
fun branchOf(value: Int, left: Node, right: Node) = Node(value, left, right)

class TwoSumIV {
fun findTarget(root: Node, k: Int) = root.find(k)
}

fun main() {
val root = branchOf(5, left = leafOf(3), right = leafOf(6))
val twoSumIV = TwoSumIV()
println("Tree has 6 -> \${twoSumIV.findTarget(root, 6)}")
println("Tree has 9 -> \${twoSumIV.findTarget(root, 9)}")
}``````
I think that if you go for the sealed class hierarchy there should be some when/smart casting involved 🙂
t

tddmonkey

04/07/2021, 8:52 AM
Not sure if you’re being serious or not?
m

Michael Böiers

04/07/2021, 8:56 AM
I just don’t see the benefit of the class hierarchy in your code. I haven’t used sealed class hierarchies much, but the main use case that I have seen is that you can write elegant when expressions using smart casting in the branches.
But of course your code is perfectly fine, it’s proper use of inheritance in terms of the “is a” criterion. I just tend to avoid using inheritance wherever possible.
t

tddmonkey

04/07/2021, 9:15 AM
I also prefer to avoid inheritance, but in this instance it’s really just an interface implemented by 2 classes. A sealed hierarchy brings the ability to control the implementations of it. It also allows me to avoid handling nulls as that’s now modelled by a
``LeafNode``
.
m

Michael Böiers

04/07/2021, 10:07 AM
Sure. This is what I meant with the when/smart cast stuff:
Copy code
``````sealed class Node {
data class Leaf(val value: Int) : Node()
data class Branch(val value: Int, val left: Node, val right: Node) : Node()

fun find(k: Int): Boolean = when (this) {
is Leaf -> k == value
is Branch -> k == value || left.find(k) || right.find(k)
}
}

class TwoSumIV {
fun findTarget(root: Node, k: Int): Boolean {
return root.find(k)
}
}

fun main() {
val root = Node.Branch(5, left = Node.Leaf(3), right = Node.Leaf(6))
println(root)
val twoSumIV = TwoSumIV()
println("Tree has 6 -> \${twoSumIV.findTarget(root, 6)}")
println("Tree has 9 -> \${twoSumIV.findTarget(root, 9)}")
}``````
t

tddmonkey

04/07/2021, 10:36 AM
Oh yeah totally, I think I just prefer moving the logic to the implementing class
m

Michael Böiers

04/07/2021, 10:58 AM
This comes down to preferences about encapsulation and object-oriented programming. I tend to gravitate more towards the functional approach. Personally I don’t think that one is better or worse than the other. 🙂 Sorry @thhh for derailing this thread a little, but I think your question had been answered before 🙂
❤️ 1
h

04/07/2021, 5:32 PM
@Michael Böiers @therealbluepandabear I think I ran into the reason why ‘var `val`’ is used 🙂 It comes from leetcode problems and probably they use it to align names with other languages:
Copy code
``````/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
*     var left: TreeNode? = null
*     var right: TreeNode? = null
* }
*/``````
🙌 2
5 Views