Fa17 CS 61B Discussion 8

Announcements

• Project 2 is due 11/9!
• HW5 is due 10/20!

Future Courses after CS61B?

• CS61B tradition: Sneak in topics from other courses.
• CS 186: Databases
• Learn all the cool tricks to make fast databases.
• CS 188: Artificial Intelligence
• Intelligent searching, AI design

Future Courses after CS61B?

• Other courses I think are cool:
• CS 162: Operating Systems
• CS 170: Algorithms
• CS 176: Computational Biology
• CS 189: Machine Learning
• Opens you up to CS 194 series on deep learning

Q4 from last time

Q4

• Error in solutions: Doing linear work in each node.
• For those of you that missed the explanation:
• Only the bottom layer of the tree is considered.
• The rest of the layers are lower ordered terms.
• The last layer is N(N - 1)(N - 2)...(1) => O(N!)

Lesson Learned

• Overconfidence in ability to solve runtime problems on the fly will lead to embarrassment

Traversals

Orders

• Given a node and its left and right children:
• Pre-order: node, left, right
• Post-order: left, right, node
• In-order: left, node, right (literally left to right)

Traversing

• This can get tricky! At every node, we must apply the same idea.

Q1 Example

• Let’s do a pre-order traversal on the tree on Q1.
• We start at the root.
• Remember, pre-order -> node, left, right.
• What’s first?

Q1 Example

• 10 is the first answer.
• Then we traverse to the left node.
• Now what?

Q1 Example

• Subtle: We actually start our traversal again.
• At node 3, we do a pre-order traversal again.
• 3 is our next answer.

Important

• Notice I did not traverse node 10 as 10, 3, 12.
• I traversed node 10 as 10, then recursive call on 3.
• Then, I traversed node 3 to get the next answer, 3.
• Now, I will recursively call on 1.

Q1 Example

• At node 1, we do a preorder traversal again.
• 1 is our next answer.
• 1 has no left child, so we do not recursively call.
• 1 has no right child, so we do not recursively call.
• Thus, we have finished the preorder traversal of node 1.

Q1 Example

• After node 1 terminates, we return to the node that called it, node 3.
• Recall we were in the middle of processing this preorder traversal. We went to 3, then went to 1.
• Now, we will traverse to 7.

Q1 Example

• At node 7, we do a preorder traversal again.
• 7 is our next answer.
• 7 has no left child, so we do not recursively call.
• 7 has no right child, so we do not recursively call.
• Thus, we have finished the preorder traversal of node 7.

Q1 Example

• After node 7 terminates, we return to the node that called it, node 3.
• Recall we were in the middle of processing this preorder traversal. We traversed 3, then went to 1, then went to 7.
• Now we are done doing the traversal of node 3.

Q1 Example

• Finally, we return back to our root. Only now, do we get to process node 12.
• Finish the preorder traversal on your own.

Again

• Notice that I traversed to the node first, before saying: “# is our next answer”.
• The act of traversing to the node does not equal being our next answer.
• To see this, let’s do the postorder traversal.

Q1 Example

• Let’s do a post-order traversal on the tree on Q1.
• We start at the root.
• Remember, post-order ->left, right, node.
• What’s first?

Q1 Example

• Well, 10 is our root, but we have to go to 3 first.
• So we traverse to 3.
• But now, we have to go to 1 first.
• At 1, we have no children.
• Our first answer is 1.
• Finish the rest of the post-order and in-order traversal.

DFS/BFS

Depth-first Search

• DFS is similar to pre-order traversal. But it is more general.
• There is no notion of left and right for DFS.
• DFS says “follow a path as far as you can.”
• We will see more DFS when we do graphs.

Depth-first Search

• In Q1, I’ve enforced that for DFS/BFS, we process nodes left to right.
• Thus, our answer to DFS is the same as the pre-order traversal.
• Do you see why?

Breadth-first Search

• Breadth first search is different from any of the orderings we’ve seen so far.
• BFS says “search all paths one level at a time.”
• Finish up Q1.

Binary Search Trees

Invariant

• Here, we introduce the idea of an invariant.
• Another word for this is property.
• For a data structure, as long as it is not performing an operation, it should maintain its invariants.

BST Invariant

• At each node n, all nodes to the left are smaller than n.
• At each node n, all nodes to the right are larger than n.
• Each node can only have two children (this is actually an invariant of a binary tree, which the BST inherits).

Discussion Q2

Q2

• First look at the code, and talk with the people around you.
• Give an example of a tree that would be incorrectly returned as a binary tree.

Q2

• Now, write the correct function.
• Oftentimes for recursive functions, we do the bulk of our recursion in a helper method. Our main method simply kicks it off.
• Use this idea.

Discussion Q3

Q3

• Same idea.
• What are the parameters of the helper function?
• Hint: You need to track the current “path” at a node.

BST Deletion

Deletion

• Go back to Q1 for the tree.
• How would we delete a node?

Deletion

• First, find the node.
• If node has no children, easy. Remove the node.
• If node has one child, remove the node and replace with child (and its subtree remains untouched).
• If node has two children...

Deletion

• Pick the right side (arbitrary).
• Find the smallest node on the right side.
• If you picked left side, then find the largest node.
• Replace the deleted node with the new node.

Deletion

• Is this recursive? Why or why not.

Deletion

• Our base cases are if a node has 0 or 1 child.
• However, if we have 2 children, then we have to perform this search.
• But due to our BST, it is impossible for the new node we find to have two children.
• Otherwise, there’s a smaller node to search for.