Lecture 5/22: Lecture 21 Q&A
Lecture 21 Questions and Answers (Exported from Zoom Q&A log)
Q: Will A6 be released around noon or no specific time?
A1: Love the enthusiasm! Saturday afternoon, say
Q: Thanks Dante!!
A1: Agreed!
Q: <3
A1: Thanks Dante!
Q: This chat is so wholesome
A1: we try!
Q: Building off doubly linked lists, is it possible for each node to have any arbitrary and differing number of other pointers to other nodes to represent an entire web/network or is there a better way to do that?
A1: Yes! One pointer, two pointers, many pointers, all have their uses depending on what kind of structure you are modeling and the relationship between nodes
Q: what’s the main advantage of using a linked list/double linked list to just an array ?
A1: Can insert/remove in middle in O(1) time (remember how you had to shuffle all the elements in an array?)
Q: why dont we need t say ListNode* cur= new ListNode?
A1: I believe newNode already was set to the newly allocated Node
Q: Can the last two steps be flipped?
A1: yes
Q: do we need to do "delete curr" at the end to delete the element?
A1: yes, to avoid making a memory leak
Q: but then we cannot delete curr? if we do remove curr this way?
A1: once we have unlinked curr, we can then deallocate the memory for that node
Q: What is the next CS class we learn about data structures?
A1: CS161 is Data Structures and Algorithms, 166 and 168 follow on with more
Q: If there are better ways than linked lists, why is Stanford's Queue class based on linked lists?
A1: LInked lists are great for a linear structure that only is added to on the ends, such as a queue or deque
Q: is there a variation of this where the edges can be undirected
A1: Yes, that structure is called a “graph”
Q: so height of leaf P is 0?
A1: Yes, height of any leaf is 0
Q: could N have 2 right children and 1 left child?
A1: A binary tree has at most 2 children, but other types of trees can have 0 to N children
Q: are leaves anything at the very bottom level of the tree?
A1: Yes. A leaf is a node with no children, it is a singleton tree, all children are nullptr
Q: are there self loop cycles?
A1: Not in a tree, no.
Q: so much tree incest!
A1: no, no tree has that (only graphs…)
Q: what is a leaf defined as again?
A1: A leaf node has no children
Q: Can you make a … doubly linked tree by adding a parent property to the TreeNode?
A1: Yes!
Q: So tree children are all stored in various random open spaces in memory because they are made up of pointers?
A1: Yes, each node has its own indivdiual space and they are scattered throughout the computer’s memory, not contiguous like arrays
Q: trie means each node is a string?
A1: In a trie, each node is often a single character and when you trace a path from root to leaf, that sequence of characters forms a word
Q: why is it allowed to have a right leaf without a left?
A1: Each node in a binary tree can have 0, 1, or 2 children. You may be thinking about the binary heap, which was required to be “complete”, where it is filled level by level and every node has 2 children other than possibly the last one which may have only the left child. That completeness property is specific to binary heaps
Q: what is in order traversing again?
A1: recursively traverse the left subtree, then visit the current node, the recursively traverse the right subtree
Q: what if a parent can have multiple nodes? do you just put multipel pointers in the struct?
A1: If you have a fixed number, 1/2/3 you probably have names for each, if there is a variable number, you might use a Set or Vector (see the NArayNode struct defintion earlier in lecture slides)
Q: if we use preorder to first traverse through left then right, how is that different than in order traversing?
A1: The difference concerns when we process the current node, either before both children (pre), inbetween the two children (inorder) or after both children (post)
Q: so preorder just means that the output is something we can reasonably interpret?
A1: For this example, yes
Q: what’s the practical use of this? couldn’t we just have arranged the numbers properly so that a preorder would have worked
A1: Wait til next lecture, more will be revealed! Binary search trees (inorder) are arranged to make it easy to add/remove values maintaining the sorted property
Q: what was the post order traversal for the number tree?
A1: 1 3 2 6 5 4
Q: How do we get to Julie’s OH?
A1: live answered
Q: https://web.stanford.edu/class/cs106b/restricted/zoom_info
A1: live answered
Q: ^^ OH link
A1: live answered