https://kotlinlang.org logo
#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
}
`set.add(root.
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

Hadji Musaev

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

Hadji Musaev

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 -> {
            set.add(n.value)
            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) {
            set.add(value)
            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

Hadji Musaev

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