# Difference between “Complete binary tree”, “strict binary tree”,“full binary Tree”?

I am confused about the terminology of the below trees, I have been studying the Tree, and didn't able to distinguish between there trees:

a) Complete Binary Tree

b) Strict Binary Tree

c) full Binary Tree

Please help me to differentiate among these trees. When and where these trees are used in Data Structure?

-
Does en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees not answer your question? –  rodion Sep 10 '12 at 21:26
no its not ,a lot of confusion among these –  kTiwari Sep 10 '12 at 21:28
Strict Binary Tree: Every node can have 2 child or no nodes at all –  vikkyhacks Feb 18 '14 at 17:44

wikipedia yeilded

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

so you have no leaves with only 1 child. Appears to be the same as strict binary tree.

here is an image of a full/strict binary tree, from google

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.

it seems to mean a balanced tree.

here is an image of a complete binary tree, from google, full tree part of image is bonus

-
Your complete tree example also fulfills the criteria of being a full binary tree so the difference is apparently blurred , in my opinion you might wanna give an example of a complete tree which is not a full binary tree and vice-versa , that would make the answer complete :) –  rohit srivastava Aug 30 '14 at 17:30

Perfect:

``````       x
/   \
/     \
x       x
/ \     / \
x   x   x   x
/ \ / \ / \ / \
x x x x x x x x
``````

Complete:

``````       x
/   \
/     \
x       x
/ \     / \
x   x   x   x
/ \ /
x x x
``````

Strict:

``````       x
/   \
/     \
x       x
/ \
x   x
/ \
x x
``````
-

Disclaimer- The main source of some definitions are wikipedia, any suggestion to improve my answer is welcome.

Although this post has an accepted answer and is a good one I was still in confusion and would like to add some more clarification regarding the difference between these terms.

(1)FULL BINARY TREE- A full binary tree is a binary tree in which every node other than the leaves has two children.This is also called strictly binary tree.

The above two are the examples of full or strictly binary tree.

(2)COMPLETE BINARY TREE- Now, the definition of complete binary tree is quite ambiguous, it states :- 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. It can have between 1 and 2h nodes, as far left as possible, at the last level h

Notice the lines in italic.

The ambiguity lies in the lines in italics , "except possibly the last" which means that the last level may also be completely filled , i.e this exception need not always be satisfied. If the exception doesn't hold then it is exactly like the second image I posted, which can also be called as perfect binary tree. So, a perfect binary tree is also full and complete but not vice-versa which will be clear by one more definition I need to state:

ALMOST COMPLETE BINARY TREE- When the exception in the definition of complete binary tree holds then it is called almost complete binary tree or nearly complete binary tree . It is just a type of complete binary tree itself , but a separate definition is necessary to make it more unambiguous.

So an almost complete binary tree will look like this, you can see in the image the nodes are as far left as possible so it is more like a subset of complete binary tree , to say more rigorously every almost complete binary tree is a complete binary tree but not vice versa . :

-

Consider a binary tree whose nodes are drawn in a tree fashion. Now start numbering the nodes from top to bottom and left to right. A complete tree has these properties:

If n has children then all nodes numbered less than n have two children.

If n has one child it must be the left child and all nodes less than n have two children. In addition no node numbered greater than n has children.

If n has no children then no node numbered greater than n has children.

A complete binary tree can be used to represent a heap. It can be easily represented in contiguous memory with no gaps (i.e. all array elements are used save for any space that may exist at the end).

-

Full binary tree are a complete binary tree but reverse is not possible, and if the depth of the binary is n the no. of nodes in the full binary tree is ( 2^n-1 ). It is not necessary in the binary tree that it have two child but in the full binary it every node have no or two child.

-
You cannot strictly say that "reverse is not possible " in fact your this very assumption is defied in the example of complete tree in the accepted answer ... you should rather say that may or may not be possible –  rohit srivastava Aug 30 '14 at 17:34
if the depth of the binary is n the no. of nodes in the full binary tree is ( 2^n-1 ): but a full binary tree definition is a tree where every node is either a leaf or has two children. So the max possible no. of children is ( 2^n-1 ) but it may be less than that. –  mrida Sep 27 '14 at 10:49

Concluding from above answers, Here is the exact difference between full/strictly, complete and perfect binary trees

1. Full/Strictly binary tree :- Every node except the leaf nodes have two children

2. Complete binary tree :- Every level except the last level is completely filled and all the nodes are left justified.

3. Perfect binary tree :- Every node except the leaf nodes have two children and every level (last level too) is completely filled.

-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://stackoverflow.com/questions/12359660/difference-between-complete-binary-tree-strict-binary-tree-full-binary-tre?answertab=votes", "fetch_time": 1427715354000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2015-14/segments/1427131299261.59/warc/CC-MAIN-20150323172139-00004-ip-10-168-14-71.ec2.internal.warc.gz", "warc_record_offset": 267910757, "warc_record_length": 20744, "token_count": 1362, "char_count": 5775, "score": 3.890625, "int_score": 4, "crawl": "CC-MAIN-2015-14", "snapshot_type": "latest", "language": "en", "language_score": 0.9426884055137634, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00018-of-00064.parquet"}