What is the difference between a full binary tree and a complete binary tree?

Question

A complete binary tree by my understanding can have incomplete nodes in the last level of the tree. What is a full binary tree? What is the difference?

Solution

A full binary tree (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children.

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Here's the source for these descriptions and a picture for reference: http://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html

Comments

[chb]

Note that the actual "source" is wikipedia, as indicated in the top, left-hand corner of the page.

[ElleryL]

regards the complete binary tree; when you say "are completely filled except possibly the last level" do you mean all nodes (possibly the parent of leaves) have two children?