Q: is it next Thursday or this Thursday
A1: This thursday
Q: there is no assignment due this week?
A1: No, A6 is due this thursday, the wording on the slide is confusing
Q: Can we talk to Chris/Julie/Chase in office hours or do we have to schedule an individual meeting?
A1: yes you can come to office hours
A2: During office hours is good, you can also post on Ed!
Q: What if we have equality?
A1: live answered
Q: do these binary trees then have limits as to how large they are based on the root? can we continue into negative numbers?
A1: There are no limits, and yes, we could have negative numbers
Q: for every node, does it have to keep track of every single node above it? For example, with the 7 you have to keep track of 4, 2, and 6
A1: live answered
A2: Nodes don’t keep track of the nocdes above them. The links in this structure flow downwards from the list.
Q: Are binary trees always going to be set up as a min heap?
A1: live answered
A2: Binary trees are distinct fro heaps. They don’t have to be completely filled and they have a different property regardnig ordering of parents and children.
Q: the base case here means the tree is empty?
A1: correct
Q: if upi pass in 2 rather than root, then u will get 4 rather than 8?
A1: live answered
A2: Sure, but we’re generally trying to find the maximum in the whole tree, which is why we always start at the root
Q: How would you do this with a loop? How do you loop thru a BST?
A1: cur = root; while (cur->right != nullptr) { cur = cur->right; } return cur->value;
A2: (need special case if tree is empty, for Set it would be appropriate to raise error)
Q: are we going to discuss how to balance the BST?
A1: live answered
Q: what makes a string lesser or greater than the root?
A1: We typically order strings lexicographically
A2: lesser means that it comes before the root in alphabetical order
A3: The < and > operators are defined on strings by alphabetical order so abc < def
Q: but we can replace 8 with 7 or we can put 7 under 8
A1: The insert algorithm will add the 7 under the 8. We don’t want to replace the 8, it should stay in the tree.
Q: if the tree is built of ints, how do we put strings or other types in the tree? Are they hashed or something?
A1: The tree nodes can only contain a single type. .If you wanted to build a tree to hold a different type you would use a differently defined tree node
A2: We typically only have tress of one type at a time (either ints or strings)
Q: How would you handle inseritng duplicate values?
A1: This is up to you, you can treat the value as less than the existing value or greater than
Q: what does arms-length recursion mena
A1: Doing work ahead of the recursive call rather than letting the existing base case hande it
Q: can we go arbitrary depth in terms of pointing to a pointer (i.e. pointing to a pointer to a pointer, and so on?) If so, is there any case where this might be useful?
A1: live answered
Q: Where is root being initialized?
A1: In the constructor of the StringSet class
A2: There is likely a constructor for the class where it gets initialized to nullptr
Q: Why do we need a count there?
A1: count is an instance variable that is part of the class that keeps track of how many elements we’ve added to the set
A2: This is antipating the need to support an efficient .size() member function
Q: how would strings be compared in the tree? Just by first first char?
A1: Typically it would be lexicographic order, i.e. s < t if s appears earlier in dictionary order
A2: strings are compared character by character starting from the beginning. If all the characters match up the stings are equal. Otherwise, for the first character that is different, then the string with the “smaller” char (that is a < b < c < … < z) is considered to be smaller
Q: how would the logic for reference to a pointer be implemented in a while loop? would it require a double pointer?
A1: It is possible to have reference variables (not just reference parameters) but we won’t go into how to do that.
Q: Do BST have repeat values?
A1: a BST can allow repeat values. In this example, Chris is implementing a Set, though, which does not have duplicates.
Q: Why is the reference passed in a reference to the nullPointer and not the 6 itself?
A1: live answered
Q: I’m still kind of confused by the idea of reference to a pointer. So is node the node itself, not a pointer?
A1: A reference to a pointer works very similar to how references to other data types work. You can use the refernce much the same as you would a normal pointer, with the main thing that is different is that when you make changes to the value of the pointer, those changes are persistent in the calling function.
A2: node is a pointer, but that pointer is being passed by reference so that inside the function we can update the poitner to point to a new memory locaiton and that change will be persistent
Q: where do we update the reference? I'm confused
A1: live answered
A2: When you assign node = …. that assignemnt is changing node to point to a new memory location
Q: Why can’t you use just a single pointer without any references in the parameter?
A1: live answered
Q: What is the advantage to use double-pointer in this case?
A1: live answered
Q: is the double pointer passed by reference?
A1: No. A parameter is passed by value unless there is a & on the parameter type
Q: We could use the double-pointer method to implement the function iteratively, right?
A1: sure, that would be possible
Q: Why do we want to delete 5?
A1: live answered
Q: if we are removing the 2, why would we delete the 5?
A1: live answered
Q: why would we delete the 5?
A1: live answered
Q: where will 5 go?
A1: live answered
Q: So would you ever need to make more than 1 recursive call?
A1: No. In the two-childre case, you are choose the min or max node from subtree, that min/max node can only have one child, so is a simple replace on that one
Q: How are you recursively moving the numbers?
A1: live answered
Q: if the leaf 4 is 7, and I want to remove 2, after replace 2 with 3, and I want to remove 3, what should I do
A1: live answered
Q: why didnt we move the 8 up?
A1: live answered
Q: So the largest element in a subtree would be the first element without a right child?
A1: Correct — refer to how the findMax function worked — go right until you hit node with no right children
Q: what balance mean
A1: live answered
Q: So only it is balanced, all those functions will be log n
A1: live answered
Q: can we balance as we're adding, or do we need to do it after we created the entire tree?
A1: live answered
Q: Going back a little bit to the add code, what’s the difference between passing in Node* &node and Node &node? What would have happened if we had just put Node &node?
A1: The former is passing a pointer to a Node, by reference means the function can update that pointer to point to a new memory location. The latter is passing as Node, by reference means the function can update the Node fields (i.e data/left/right)
Q: shouldn’t 11.5 be to the right of 11?
A1: live answered
Q: Does it matter which approach we take? - largest of the left or smallest of the right?
A1: live answered
Q: How do people come up with such algorithms?
A1: Lot’s of persistence and clever brainstorming!