[CS 61A SU26] Lab 7 Problem Getting Started Add Leaves

[00:00:02]hi everyone I'm Jose and I'm going to be getting you started for question four on problem seven here we're going to be implementing add the leaves which is a function which takes in a tree and a number V and what this function is going to do is that for every node in the tree depending on the depth that it is at it will add depth number of leaves to that node right and so here we see we took in a tree with root node or depth zero node one and then um actually let me do this so note that depth 0 is just this node one nodes at depth one where three and two and nodes are depth two were this node four and here we see that we added zero leaves to the node one we added one leaf to nodes three and two and we added two leaves to node four in this case v was five and that's what we're going to try to implement with our function so I think the first thought that comes to our mind is that well first of all what we should do is just have a recursive call a recursive function right that adds in the leaf to the knowledge your ad and then uh recurses through the branches of that node and adds in their respective views as well but that's going to be a problem because if we see here well we started one and we added zero leaves to one and then we recurs through this branches well that sounds pretty good but then we see that we would start at three add in the branches and then add in the branches for two as well but now we would say well now recurse over the branches of three and two and add in leaves for those branches and what would happen is that not only were you add in uh uh leaves for four which is appropriate in this case you would also what you were recursing through the branches of three adding leaves for five which is a problem we don't want these leaves here right we want these last two leaves um not to be there these are incorrect and so what we should do here is that we should first we add the leaves to the branches of the node that we're at and then we add the appropriate number of leaves to the node aware and another thing that's very important here is to keep track of the depth of course we only know the number of leaves to add to to a null that we're at based on the depth and what we're going to have to do here is have a helper function to help us out keep track of the depth while we recursed through the Stream so what I suggest to you is have a helper function which takes in a tree and the depth that this tree is currently at right because each branch of a node right here let's say we have we're looking at node one each branch of this node is a tree itself right so this is a tree and this is a tree just so happens in this case that these trees are very simple right two is even a one node tree but they are tree objects themselves and so for each node what I suggest is you um with their helper function pass in the branches as tree and the depth plus one and then for those trees add in the leaves for the branches first before adding in the leaves for the for the root node itself right and so for example we would start here at one we would say oh add in the leaves for three then add in the leaves for two and only then add in the leaves for the root right so we start at three then we go to two and then we go to one and when we uh when we say add in leaves for three what we what's actually going on is we add in leaves to the branches of three which is four in this case so we add those leaves in and then we add in the leaves for the node that we're currently at and then this recursive call would be over we add in the leaves for the other branch of one and only then do we add in the leaves for the root node which in fact is you and how we would start this recursive call is we would say helper of we pass in the original tree and the depth zero right and then from there it starts and makes recursive calls to each one of the branches before adding in the notes itself um and yeah I I hope I managed to get you started on this question hope that was helpful and I hope that you had a good spring break I'll see you guys in the next one bye bye