Difference between Complete binary tree strict binary tree full binary Tree

Question

I am confused about the terminology of the below trees  I have been studying the Tree  and I am unable to distinguish between these 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

User · Answer

To start with basics  it is very important to understand binary tree itself to understand different types of it   A tree is a binary tree if and only if  -      It has a root node   which may not have any child nodes  0 childnodes  NULL tree      Root node may have 1 or 2 child nodes   Each such node forms abinary tree itself       Number of child nodes can be 0  1  2       not more than 2     There is a unique path from the root to every other node  Example            X                   X      X                          X     X   Coming to your inquired terminologies   A binary tree is a complete binary tree   of height h   we take root node as 0   if and only if  -  Level 0 to h-1 represent a full binary tree of height h-1      One or more nodes in level h-1 may have 0  or 1 child nodes  If j k are nodes  in level  h-1   then j has more child nodes than k if  and only if j is to the left of k   i e  the last  level  h   can be  missing leaf nodes  however the ones present must be shifted to the left  Example                              X                                                                                                                             X                    X                                                      X       X             X       X                                                       X    X   X   X        X    X    X   X    A binary tree is a strictly binary tree if and only if  -  Each node has exactly two child nodes or no nodes  Example             X                    X     X                           X      X                            X   X  X   X    A binary tree is a full binary tree if and only if  -  Each non leaf node has exactly two child nodes  All leaf nodes are at the same level  Example                              X                                                                                                                             X                    X                                                      X       X             X       X                                                       X    X   X   X        X    X    X   X                                                       X   X X  X X X X X     X  X  X X  X X X X    You should also know what a perfect binary tree is   A  binary tree  is a perfect binary tree if and only if  -      is a full binary tree      All leaf nodes are at the same level  Example                              X                                                                                                                             X                    X                                                      X       X             X       X                                                       X    X   X   X        X    X    X   X                                                       X   X X  X X X X X     X  X  X X  X X X X    Well  I am sorry I cannot post images as I do not have 10 reputation  Hope this helps you and others

User · Answer

Let us consider a binary tree of height  h   A binary tree is called a complete binary tree if all the leaves are present at height  h  or  h-1  without any missing numbers in the sequence                       1                                      2       3                                      4        5   It is a complete binary tree                       1                                      2       3                                     4         6       It is not a complete binary tree as the node of number 5 is missing in the sequence

User · Answer

full binary tree is full if every node has 0 or 2 children   in full binary number of leaf  nodes is number of internal nodes plus 1                       L l 1

User · Answer

Complete Binary Tree  All levels are completely filled except the lowest level and one main thing all the leaf elements must have left child  Strict Binary Tree  In this tree every non-leaf node has no child i e  neither left nor right  Full Binary Tree  Every Node has either zero child or Two children  never having single child

User · Answer

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

User · Answer

In my limited experience with binary tree  I think   Strictly Binary Tree Every node except the leaf nodes have two children or only have a root node  Full Binary Tree  A binary tree of H strictly or exactly  containing 2  H 1  -1 nodes   it s clear that which every level has the most nodes  Or in short a strict binary tree where all leaf nodes are at same level  Complete Binary Tree  It is a binary tree in which every level  except possibly the last  is completely filled  and all nodes are as far left as possible

User · Answer

There is a difference between a STRICT and FULL BINARY TREE    1  FULL BINARY TREE  A binary tree of height h that contains exactly  2 h -1 elements is called a full binary tree   Ref  Pg 427  Data Structures  Algorithms and Applications in C    University Press   Second Edition by Sartaj Sahni    or in other words  In a FULL BINARY TREE each node has exactly 0 or 2 children and all leaf nodes are on the same level   For Example  The following is a FULL BINARY TREE             18                         15       30                             40    50  100  40    2  STRICT BINARY TREE  Each node has exactly 0 or 2 children   For example  The following is a STRICT BINARY TREE            18                        15       30                          40    50   I think there s no confusion in the definition of a Complete Binary Tree  still for the completeness of the post I would like to tell what a Complete Binary Tree is   3  COMPLETE BINARY TREE  A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible   For Example  The following is a COMPLETE BINARY TREE              18                         15         30                          40    50    100   40           8   7  9    Note  The following is also a Complete Binary Tree            18                        15       30                             40    50  100  40

User · Answer

Wikipedia yielded  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 nodes 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

User · Answer

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

User · Answer

Perfect Tree          x                           x       x                x   x   x   x                 x x x x x x x x   Complete Tree          x                           x       x                x   x   x   x       x x x   Strict Full Tree          x                           x       x         x   x              x x

User · Answer

Concluding from above answers  Here is the exact difference between full strictly  complete and perfect binary trees   Full Strictly binary tree  - Every node except the leaf nodes have two children Complete binary tree  - Every level except the last level is completely filled and all the nodes are left justified  Perfect binary tree  - Every node except the leaf nodes have two children and every level  last level too  is completely filled

User · Answer

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

[data-structures] Difference between "Complete binary tree", "strict binary tree","full binary Tree"?

Examples related to data-structures

Examples related to tree

Examples related to binary-tree