views:

47

answers:

2

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?

+4  A: 

I don't completely understand where your confusion lies but I'll do my best to answer...

A binary tree is considered full if every node has exactly 0 or 2 children.

A binary tree is considered complete if every level is full except the last, and all nodes are pushed as far left as possible.

So if it fits both of these descriptions, which is possible, it can simultaneously be full and complete.

Also, a binary tree is considered perfect if it is full and all leaves are on the same level.

So in the example you drew out above, that tree is full and complete, but not perfect.

I hope this helps.

JRam930
My confusion lay with not being sure whether a tree can be simultaneously full and complete. The book definition was not clear on this point, and seemed to contradict other things I had read on the web.
Jason
Well I hope this helped. Good luck on your midterm!
JRam930
+2  A: 

Some more examples which will hopefully be helpful:

Complete, not full:

        R
      /    \
     L      T
    / \    / \
  I    N   S   U
 / \  /
A  E O   

Full, not complete:

        R
      /    \
     L      T
    / \    / \
  I    N   S   U
      / \
     O   P


        R
      /    \
     L      T
    / \    
  I    N   
 / \  / \
A  E O   P
outis
This is where the text examples fell short, because the description for a complete tree was like your first example, except with a right node of N and a left node of S, made it seem as if the authors were saying trees can't be full and complete.
Jason