Week - 15

Quiz on trees:

1. Given two binary search trees, check whether or not they are identical.  Identical meaning that both the structures (node location, height, etc.) and the values contained at corresponding nodes are matching. 
2. Given a value k, and a binary tree T, print out all values at k distance from the root.
3. Given a binary search tree T and an integer k, find the node in T with the closest value to k.  E.g. if the binary tree contained 20, 23, 30, 34, 40, 51, 54, 60, 70, and k = 31, then the solution should return the node containing 30.  (We will deal with integers in this case, so no generics.)

 Answers link

Week - 14

Post order traversal of a BST: Link to code

Quiz

Week-13 : Correction in priority queue

Today, we discussed about implementing priority queue using ArrayList and LinkedList. While using ArrayList, we don't have to shift elements after removeMin(). I have explained a better solution below.

When we are using

Unordered ArrayList:

• add(element e) => O(1)
• peekMin() => O(n)
• removeMin() => O(n)
• Here, removeMin() requires finding the min value => O(n), removing it and then, shifting the elements will take O(n).
• A better solution: Instead of shifting, just replace the gap with the last element of the ArrayList. This can be done in constant time [O(1)].

Unordered ArrayList with index value of min:

• add(element e) => O(1)
• peekMin() => O(1)
• removeMin() => O(n)
• Again instead of shifting, replace the gap with the last element. But, we have to keep track of the index of min. To update the min index, we must traverse the list. This will take O(n) time.

Week - 13

Sets & MultiMap

1. Link to presentation slides
2. Set interface code
3. ListSet code

Week-12 - Midterm II: Solutions

Problem 1:

In order to get a worst case running time of O(n^2), we should draw a tree in such a way that, depth() function is called at each level. Therefore, a tree with many leaves will run for the worst case.

Problem 2

ArrayList : O(n) for remove => O(n^2) run-time.
LinkedList: O(1) for remove => O(n) run-time

Reference: ArrayList Vs LinkedList

Problem 3

Code

Problem 4

Inorder and Breadth first traversal.

Problem 5

Code

Week-11

Class cancelled.

Week-10

We discussed 2 topics:

1. HashMap example: Roman Calculator example
2. Implementing stack using 2 queues. Link for more details
3. Quiz