Week 5

Question 1

Depth

Answer 1

Minimum number of edges between root and given node n.
Number of ancestors of n, other than n itself.
Depth of n = 1+ depth of parent
-> Wie tief bin ich -> schaue hoch

Question 2

Height

Answer 2

Maximum Depth of leaf nodes of given subtree with root n
Number of edges on longest path from root to a leaf
-> wie Hoch bin ich. Schaue runter

Question 3

Binary Tree

Answer 3

• every node has 2 children
• either none, both or one of the children is null
• nodes do NOT have to be order (vs. BST)
• full BT all nodes have children with no null or both null

Question 4

Running time of searching in BST

Answer 4

proportional to height of the Tree.

Expected height: O(log n)

Question 5

HashSet vs TeeSet

Answer 5

TreeSets implemented with BST
Adding, Removing, containing all O(1) with Hashset while TreeSet it is O(log_2 n)
TreeSet better if I need the data in sorted order
Remember: Set has no duplicates

Question 6

Ways to Traverse BST

Answer 6

• in order: left, print, right
• pre-order: print, left, right
• post-order: left, right, print

Question 7

What is the problem with maintaining a sorted linked list?

Answer 7

Adding to a sorted linked list is an O(1) operation.
In the worst case, we would have to put the newly inserted value toward the end of the list and compare it to all other elements, which would be O(n).

Question 8

What is a benefit of using a TreeSet over a HashSet? Select

Answer 8

TreeSet’s contains() function has a better worst case scenario than HashSet

In the worst case, a TreeSet’s contains() is O(log n) whereas a HashSet could potentially take O(n) since a TreeSet’s data is stored in sorted order and self balancing mechanism. The primary benefit is that a TreeSet maintains the sorted order of its elements, whereas a HashSet does not.