In preparation for the data structures midterm, the professor gave us last year's test, one question which deals with re-arranging an example tree into a complete binary search tree. I've tried several different versions of writing out the tree, but this complete binary tree example from Wolfram Mathematica didn't help at all, since it also fits the definition of full. The textbook defines a complete binary tree as a tree through level n-1 is perfect with some extra leaf nodes at level n, all left aligned.
The nodes are A E I L N O P R S T U
, n=11 nodes. Here's the best answer I came up with:
R
/ \
L T
/ \ / \
I N S U
/ \ / \
A E O P
But this fits the example of the tree at WM, but not the book example. So which is the correct answer?