I'm doing a Recursion call to print out a the values of a tree in a mutable list. But I am getting this NullPointerException error.

Exception in thread "main" java.lang.NullPointerException
    at udacity.TreesPraticeKt.DFSRecursive(TreesPratice.kt:29)
    at udacity.TreesPraticeKt.DFSRecursive(TreesPratice.kt:29)
    at udacity.TreesPraticeKt.DFSRecursive(TreesPratice.kt:29)
    at udacity.TreesPraticeKt.main(TreesPratice.kt:63)
    at udacity.TreesPraticeKt.main(TreesPratice.kt)

I tried addressing it with an if statement, but it doesn't work

Here's the code

class TreeNode<T>(var key: T){
    var left: TreeNode<T>? = null
    var right: TreeNode<T>? = null
}

/** Recursive Function */
fun DFSRecursive(root: TreeNode<Char>) {
    if(root == null) return
    val results = mutableListOf<Char>()
    DFSRecursive(root.right!!)
    DFSRecursive(root.left!!)

    results.add(root.key)

    return println(results)

}

fun buildTree(): TreeNode<Char>{
    val a = TreeNode('a')
    val b = TreeNode('b')
    val c = TreeNode('c')
    val d = TreeNode('d')
    val e = TreeNode('e')
    val f = TreeNode('f')


    a.left = b
    a.right = c
    b.left = d
    b.right = e
    c.right = f

    return a
}

the Output should be: [a, b, d, e, c, f]

But without checking for the null, it just keeps showing that error. Thank you and Any help is appreciated.

CodePudding user response：

You are checking for a null too late.

You shouldn't check whether root is null. That can never happen, because root is of a type TreeNode<Char>, not TreeNode<Char>?. Your IDE should issue a warning saying that:

Condition root == null is always false

Instead of checking for root == null, check for root.left and root.right before you recurse.

Usually in Kotlin, when you encounter NullPointerException, you ough to look for !!. Most of the time the problems lie there. This is also the case here.

You should use ?.let { } here:

fun DFSRecursive(root: TreeNode<Char>) {
    val results = mutableListOf<Char>()
    root.right?.let { DFSRecursive(it) }
    root.left?.let { DFSRecursive(it) }

    results.add(root.key)

    return println(results)
}

This change effectively recurses to the left only if the exists the left subree (root.left is not null) ad recurses to the right only if there exists the right subtree (root.right is not null).

After some follow-up questions, I decided to propose a modified implementation of DFSRecursive():

fun DFSRecursive(root: TreeNode<Char>) {
    println(root.key)
    root.left?.let { DFSRecursive(it) }
    root.right?.let { DFSRecursive(it) }
}

The above implementation prints the elements in the in-order ordering (which you specified as desired) and does not have the seemingly useless list created just for one element per call.