The return value dosn't give me a number in Kotlin

OEThe11 0
Viewed 38

This question is to find the sum of the longest path of a tree in recursion. Here is my code that I have come up with.

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

fun maxPathSum(root: TreeNode<Int>): Int{
    val leftChildPath = (root.left?.let { maxPathSum(it) } ?: Int.MIN_VALUE)
   val rightChildPath = (root.right?.let { maxPathSum(it) } ?: Int.MIN_VALUE )
    val maxChildPath = leftChildPath + rightChildPath

    return root.key + maxChildPath
} 

fun buildTree3(): TreeNode<Int>{
    val one = TreeNode(1)
    val two = TreeNode(2)
    val three = TreeNode(3)
    val four = TreeNode(4)
    val five = TreeNode(5)
    val eleven = TreeNode(11)

    five.left = eleven
    five.right = three
    eleven.right = four
    eleven.left = two
    three.right = one

    return five
}

The output I got was this.

-------Max Root to Leaf Path Sum-------
-2147483622

Not sure if it's the address of the node or not but he expected answer is 20. Thanks in advance.

binary-tree algorithm kotlin
1 Answers

Here's your tree

      5
     / \
    11  3
   /  \  \
  2    4  1

Here's your maxPathSum for each, when you use 0 for the "no branch" value

      26
     /  \
    17   4
   /  \   \
  2    4   1

You're basically just summing the value of every node, that's why you get 26. 20 is the maximum weight of a single path to a leaf node in your graph. It seems like that's what you're trying to find, the heaviest / most expensive path.

Look at your 11 node for example, where its branches are both leaf nodes - the max weight of both paths is just their actual values:

  11
 /  \
2    4

What's the most expensive path through eleven? What specific value should eleven be returning here, and why? How would you code that? (I'm getting you to think about it because this feels like homework)

And yeah, adding the largest negative number an Int can represent to itself is going to give you wild behaviour, it'll just wrap around to the largest positive as it overflows. Why would you want such a huge number anyway? What weight does a non-existent node have?

Using Int.MIN_VALUE can be useful as a way to define a value so extreme everything else will be higher than it, like a default value that will never be used because something else will immediately replace it as the "highest value".

But if there's a possibility you'll actually be returning that value, you probably want a better fallback that makes more sense as a default. In your case, since you're adding that value to your root's value, does negative 2 billion make sense in that situation? Or zero? You said in the comments that it "worked for you in a similar problem" - you have to know why it worked and why you were doing it though! Being able to think this stuff through is important

cactustictacs0
Related