Can a binary search tree be both full and complete?

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

Full Tree: a binary tree T is full if each node is either a leaf or possesses exactly two child nodes.

      O
     / \
    O   O
   / \ / \
  O  O O  O
    / \
   O   O

Full tree but not complete

Complete Tree: a binary tree T with n levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.

       O
      / \
     O   O
    /
   O

Complete tree but not full

Similarly, another example

      O
     / \
    O   O
   / \ / \
  O  O O  O
 /\ /
O O O

I hope these are helpful !