#1

#2

(Sedgewick & Wayne) Give pseudocode for a binary search tree method height) that computes the height of the tree. Develop two implementations: the first, a recursive method (which takes linear time and space proportional to the height), and the second, a method that adds a field to each node in the tree (and takes linear space and constant time per query) Recall that the balance factor of a node v is bf (v)height(v.right)-height(v.le ft) Whenhas a right child but no left child, it is bf (v)-1height(v.right), and when v has a left child but no right child, it is bf(v) (1height(v.left)), and if v is a leaf it is 0. We might write this as height(.right) - height(v.left) 1 + height (v.right) if v has both children if v has only a right child if v has only a left child if v is a leaf bf(v)-1 (1 +height(v.left)) Annotate each node of the following binary search tree with its balance factor