Binary Search Trees

Question 1

What do the methods successor and predecessor do?

Answer 1

successor(k): brings back an iterator of all of the entries with keys that are greater than k
predecessor(k): with keys less then k

Question 2

state 2 properties of binary search trees

Answer 2

1. the left child must be smaller than the root, the right child must be larger than the root
2. External node do not store anything

Question 3

Provide steps on how the insert method works in this context

Answer 3

insert(k,o)

1. search k
2. assume w is the last node reached by the search
3. Insert k at w and expand that into an internal node

Question 4

provide steps to remove a node in a BST

Question 5

Height of a BST implemented dictionary?

Answer 5

O(n) in worst and O(logn) at best