[CS 61A SU26] Lab 7 Problem Maximum Path Sum Getting Started

[00:00:00]SATWIKA PAUL: Hello, welcome to the homework  4 video walkthroughs. This is question 3, which is the maximum path sum. Here, we're  writing a function that takes in a tree and returns the maximum sum of the values  along any root-to-leaf path in the tree. So, what a root-to-leaf path is, is that here I've  basically drawn out one of the trees from the doc-tests. That's over here. Here, you can  see that 1 is the root of this tree. So, the root-to-leaf path will be a sequence of  nodes starting at the root, so here at 1, and then proceeding to some leaf of the tree. An  example here would be if you go from 1 to 5 to 3, so you've hit a leaf, or you could go from 1 to  10 because you've also hit a leaf there. Your goal is to find the maximum route to a leaf  path sum. So here, we can kind of see that if we go from one to five to three, that's going  to return a sum of 1 plus 5 plus 3, which is 9. And if we go from one to five to one, that's  going to return a sum of 1 plus 5 plus 1, which is 7. And if we go from one to ten, that returns a  sum of 11. So this is our winner because that's the maximum value. So in this case, what we want  to be doing is thinking in terms of recursion. So what I mean by that is, since we're working with a  tree, a tree is a recursive data structure, right?

[00:01:36]There are trees inside the tree's branches itself.  So what we can kind of make of that is that like here, one has the branches five and ten. Ten  itself is a tree, and this here itself is also a tree. And then if we look at five's branches, one  can be a small tree, and then three can also be a small tree. So hopefully, this gets you thinking  about how can I have recursive calls to this main function to get the max path sum on one's branches  that are trees itself. And a hint that I'll give you guys is regarding the base case of this. So  I want you guys to think about if the base case is, what if the tree just had a root, no branches?

[00:02:39]So what would we do here? In this case, like say  we were just working with a tree that had just a value of one, and we were trying to calculate  the maximum path sum. Well, in that case, there's no other leaves to go to, right? So the maximum  path sum would just be the root itself. So that's hopefully a helpful base case. Like, what would  you do if the tree was just a root? And yeah, so hopefully that gets the ball rolling on the  base case. And for the recursive call, I would say think about how you can get the maximum path  sum for each of these miniature trees included in the overall tree itself so that you can find  the overall maximum root-to-leaf path sum.

[00:03:20]So yeah, hopefully that makes  sense, and thank you for watching.