Question 6 ...  COMP1927 14s2 Final Exam


A.  (search path)

20,11,16,18


B.  (level-order traversal)

20,11,32,4,16,25,36,3,7,13,18,21,28,33,39


C.  (#nodes in perfectly balanced tree)

height = 1, nnodes = 1
height = 2, nnodes = 3
height = 3, nnodes = 7
...
height = n, nnodes = 2^n - 1


D.  (after rotateL)

root = 32, left = 20, right = 36


E.  (after deleteRoot)

root = 21, left = 11, right = 32