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

[00:00:00]SATWIKA PAUL: Hello, this is question  4 of the homework 4 video walkthroughs, and it's about "Has path." Here, we're writing a  function called "has path" that takes in a tree "t" and a string variable, which is "word." Every  node in "t," our tree that we're working with, has a label that is one character. So, we're  basically working with a bunch of one-character strings as our tree's nodes. "Has path" is the  function we're writing, and it will return true if there's a path in our tree starting from the root  and going down to all of its branches. If there's a path that spells out the given "word" parameter,  then it returns true; otherwise, it returns false.

[00:00:50]Here, I've drawn out one of the trees  from the doc-testS right here. So, we can work through some of the doc-tests. For  example, if we do "has path" of "greetings" and our string "word," in this case,  is just "H." If we start at the root, clearly, "H" matches the letter "H," so  we know we have a match right there. So, this would return true. Now, if we move on  to the next doc test where our string "word" is "I," if we look at the root, we see that  "H" does not match the letter "I," right? So, we can immediately mark that as false because  the root did not match with our first letter.

[00:01:32]Let's move on to this doc test, where the  string "word" passed in is "hello." Here, I can start at the root, and I see "H" matches  the first letter of "hello," so we're good to go there. Then I look at "H's" branches, and  I see that there's an "e," which matches the second letter of "hello," so we're also good  to go there. I go through the rest of the tree, I find an "L," which matches the "L" in "hello."  I find another "L," which matches the second "L" in "hello," and I find another "o," which  matches the last letter in "hello." So, I successfully found a path from the  root to the leaf that spells "hello."

[00:02:11]An example here that returns false is if  you look at the doc test with "by." Clearly, again, we don't have a "b" in our root, so we can automatically mark that as  false. And a hint: we do have "i," "h," and then "H's" branches have an "I," but  we don't have an "n." So, that's also false.

[00:02:31]So, I would say, again, for this problem, think  in terms of recursion because we're working with trees, so it makes it super easy to call  recursion. A good base case to start off with is to think about what we would do if the root  doesn't match anything, especially the first letter in the "word" string. If we automatically  know that our root doesn't correspond to the very first letter in the "word," then we can mark  the return value of the function as false. We automatically know that we're not going to find a  match since the first letter didn't match up. So, hopefully, that's a helpful base case. For the  rest of it, work with the remaining letters.

[00:03:15]Whatever letters you have left to match up,  do they match for the branches? So, hopefully, this helps you think of a recursive call of  how you can call the "has path" function on the branches of your root and go from there, seeing  if you're matching letters along the path to spell out the given "word." And yeah, hopefully,  that helps, and thank you so much for watching.