Help me understand the logic why the code is not r...

# getting-started

[thhh]

Help me understand the logic why the code is not returning false boolean here at once.

Details in thread

[thhh]

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")
}

[Hadji Musaev]

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.

[tddmonkey]

Why do you think it should only be printed once? By my reckoning it should be printed twice

[Hadji Musaev]

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

[Michael Böiers]

`var `val`` … seriously?

[therealbluepandabear]

Change 'val' to 'value'; seriously, it's beyond bizarre.

[Michael Böiers]

Here’s a clean version of the code. Just for fun 🙂 https://pl.kotl.in/J-JC4bMLL

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)}")
    }
}

[tddmonkey]

No sealed class hierarchy for the Nodes? 😄

[tddmonkey]

And tbh, I find (ha!) your find method to be much harder to read than the original

[Michael Böiers]

I misread that - thought you meant the with, which was a little over the top.

[tddmonkey]

I do now wonder if a sealed class hierarchy (Node, NoNode, SomeNode) might clean that up

[Michael Böiers]

What do you mean - the nullable children?

[Michael Böiers]

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.

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)}")
    }
}

[Michael Böiers]

Damn, refactoring is like a rabbit hole. 😉

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)}")
    }
}

[tddmonkey]

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)}")
}

[Michael Böiers]

Isn’t this more concise?

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)}")
}

[Michael Böiers]

I think that if you go for the sealed class hierarchy there should be some when/smart casting involved 🙂

[tddmonkey]

Not sure if you’re being serious or not?

[Michael Böiers]

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.

[Michael Böiers]

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.

[tddmonkey]

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 .

[Michael Böiers]

Sure. This is what I meant with the when/smart cast stuff:

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)}")
}

[tddmonkey]

Oh yeah totally, I think I just prefer moving the logic to the implementing class

[Michael Böiers]

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 🙂

[Hadji Musaev]

@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:

/**
 * 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
 * }
 */