Full vs. Complete Binary Tree: What’s the Difference?

In computer science, a tree is a data structure that consists of nodes connected by edges. A tree can have many different shapes and sizes, but two common types of tree data structures are full binary trees and complete binary trees. A full binary tree is one in which every node has either zero or two children (nodes that are connected directly below another node). A complete binary tree is one where all levels are fully filled except possibly the last level.

Understanding the difference between these two types of trees can be useful in a variety of contexts, including algorithms and data storage.

But first, let’s define what a binary tree is.

What Is a Binary Tree?

A binary tree is a tree data structure where each node has a maximum of two children, known as the left child and right child. It is a non-linear and hierarchical data structure; data in a binary tree isn’t stored sequentially, but it is stored based on hierarchical, parent-child relationships. Binary trees tend to be used for data storage, sorting (i.e. tree sort) and search applications (i.e. binary search tree).

In a binary tree, nodes with children nodes are called parent nodes. The topmost node in a binary tree is called the root node, and nodes with no children are called leaf nodes (leaves or external nodes). Each row of nodes in a binary tree is called a level, with the root node starting at level 0, the next level down being level 1 and so on.

There are multiple types of binary tree data structures, including:

• Full binary tree
• Complete binary tree
• Perfect binary tree
• Balanced binary tree
• Degenerate binary tree

Full binary trees and complete binary trees are some of the most common binary tree structures, so let’s explore them further.

What Is a Full Binary Tree?

A full binary tree is a binary tree data structure where each node has either zero or two children. This means that all of the nodes in the tree are either leaf nodes (nodes without children) or internal nodes (nodes with children).

Full trees have a distinct advantage when binary decisions are integral to the application. In decision-making algorithms, a full tree ensures that every node presents only two paths, reflecting a “yes” or “no” choice. This binary branching facilitates straightforward and predictable processing, streamlining traversal through the tree.

Here is an example of a full tree:

        1
       / \
      2   3
     / \ 
    4   5 
       / \
      6   7

In this tree, every node has either zero or two children, so it’s a full tree.

Full Binary Tree Theorem

The full binary tree theorem states that in a non-empty, full binary tree, the number of internal nodes is always one less than the number of leaf nodes (or the number of leaves is always one more than the number of internal nodes). If you know at least one of the three: the number of nodes (N), the number of leaves (L) or the number of internal nodes (I) — you can determine the number of the other two types of nodes in the tree. 

The theorem is as follows:

Let T be a non-empty, full binary tree Then:

1. If T has I internal nodes, the number of leaves is L = I + 1. 
2. If T has I internal nodes, the total number of nodes is N = 2I + 1. 
3. If T has a total of N nodes, the number of internal nodes is I = (N – 1)/2.
4. If T has a total of N nodes, the number of leaves is L = (N + 1)/2. 
5. If T has L leaves, the total number of nodes is N = 2L – 1. 
6. If T has L leaves, the number of internal nodes is I = L – 1.

More on Data ScienceHow Database B-Tree Indexing Works

What Is a Complete Binary Tree?

A complete binary tree is a binary tree data structure where all of the levels are fully filled, except for possibly the last level. The last level of a complete tree should be filled from left to right.

Complete trees are effective when space optimization and consistent node placement are important. These trees ensure that each level is filled entirely before populating the next, boosting storage optimization and allowing for swift operations like node addition or removal.

Here is an example of a complete tree:

        1
       / \
      2   3
     / \ / \
    4   56  7
   /
  8

More on Data ScienceHow to Implement Binary Search in Python

Differences Between Full and Complete Binary Trees

Full binary trees and complete binary trees are both common types of tree data structures in computer science. The key differences between these two types of trees are the number of children that each node can have, the way that the nodes are organized and how efficiently they can store data.

1. Number of Children Per Node

In a full binary tree, every node must have either zero or two children. In a complete binary tree, every internal node must have exactly two children, except for the last level where nodes can have between zero and two children. The nodes in the last level must also be left-filled (filled from left to right).

2. Node Organization

In a full tree, the nodes can be organized in any way, as long as every node has either zero or two children. In a complete tree, the nodes must be organized in a specific way, with all levels fully filled except for possibly the last level.

3. Computational Efficiency

In some scenarios, complete binary trees can be more computationally efficient than full binary trees. This is because a complete binary tree fills the nodes in all its levels except possibly the last. Meanwhile, a full binary tree can have nodes with zero children, meaning it might not utilize all of its possible storage space like a complete binary tree could. 

A complete binary tree’s storage capacity make it efficient for heap data structures and priority queues.

Full Binary Tree and Complete Binary Tree Example in Python

Now let’s visualize how to code full binary trees and complete binary trees in Python. We will also go over how to check whether a tree is actually full and complete, and how to perform inorder tree traversal on each.

How to Create a Full Binary Tree in Python

#creating a class to represent a binary tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        
#creating the full binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)

Checking for a Full Binary Tree in Python

#define function to check if a full binary tree
def is_fulltree(root):
    if root is None:
        return True
    if (root.left is None and root.right is not None) or (root.left is not None and root.right is None):
        return False
    return is_fulltree(root.left) and is_fulltree(root.right)

#printing result of the checking function
if is_fulltree(root):
    print("This is a full binary tree.")
else:
    print("This is not a full binary tree.")

Performing Inorder Tree Traversal on a Full Binary Tree in Python

#define function for inorder traversal of the tree
def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.data, end=" ")
        inorder_traversal(root.right)

#displaying the tree traversal
print("Inorder Traversal: ", end="")
inorder_traversal(root)

#Output for example full binary tree: 'Inorder Traversal: 4 2 5 1 6 3 7'

How to Create a Complete Binary Tree in Python

#creating a class to represent a binary tree node
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        
#creating the complete binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)

Checking for a Complete Binary Tree in Python

#define function to count number of nodes
def node_count(root):
    if root is None:
        return 0
    return (1 + node_count(root.left) + node_count(root.right))

#define function to check if complete binary tree
def is_completetree(root, index, node_amount):
    if root is None:
        return True
    if index >= node_amount:
        return False
    return (is_completetree(root.left, 2 * index + 1, node_amount) and is_completetree(root.right, 2 * index + 2, node_amount))

#define node_total and initialize index variable
node_total = node_count(root)
index = 0

#printing result of the checking function
if is_completetree(root, index, node_total):
    print("This is a complete binary tree.")
else:
    print("This is not a complete binary tree.")

Performing Inorder Tree Traversal on a Complete Binary Tree in Python

#define function for inorder traversal of the tree
def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.data, end=" ")
        inorder_traversal(root.right)

#displaying the tree traversal
print("Inorder Traversal: ", end="")
inorder_traversal(root)

#Output for example complete binary tree: 'Inorder Traversal: 4 2 5 1 6 3'