4

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?

praxmon
  • 5,009
  • 22
  • 74
  • 121
  • A Full Binary Tree is Where Every node has two child except Leaf Node we have. A Complete Binary Tree Where till Second last element all have two child.and last element may have one child but it sholud be on left side. For more things you can see more pictures on google and other sites. – Sandeep Singh Jun 06 '17 at 09:01
  • Possible duplicate of [Difference between "Complete binary tree", "strict binary tree","full binary Tree"?](https://stackoverflow.com/questions/12359660/difference-between-complete-binary-tree-strict-binary-tree-full-binary-tre) – Bernhard Barker Sep 13 '17 at 12:29

3 Answers3

4

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

Raevik
  • 1,945
  • 9
  • 32
  • 53
  • Note that the actual "source" is wikipedia, as indicated in the top, left-hand corner of the page. – chb Dec 03 '18 at 21:59
1

Perfect Binary Tree: 1. All the Internal nodes must having two children. 2. All the leaf nodes are at the same level.

Example :

         A1
     B1       B2
  C1    C2  C3  C4

Complete Binary Tree: All the levels are completely filled except possibly the last level

Example :

         A1
     B1       B2
  C1    C2  C3  C4
D1  D2 D3

Full Binary Tree: Simply Every node has 0 or 2 children.

Example :

         A1
     B1       B2
  C1    C2  C3  C4
D1  D2

Do update if the answer is aggree

Tamil.S
  • 403
  • 3
  • 14
  • 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? – ElleryL Mar 14 '20 at 16:36
0

A complete binary tree is the most balanced tree for any no. of nodes. A full binary tree is what the most balanced tree would be if you have exactly (2^n) -1 nodes. Also, by convention, the empty space in a complete binary tree is kept at the right of the tree. edit: by most balanced, i mean the one with least depth for given no. of nodes.

as g
  • 55
  • 6