Full Binary Trees

---

A Full Binary Tree is a specific type of binary tree where every node has either 0 or 2 children. It is a highly structured tree and is an important concept in computer science. Full binary trees are used in various algorithms and applications, including heap-based data structures and expression evaluation.

---

What is a Full Binary Tree?

A Full Binary Tree (also known as a Proper Binary Tree or 2-Tree) is a binary tree where every node, except the leaves, has exactly two children. This means:

• Each internal node has exactly two children.
• All leaf nodes (nodes with no children) are at the same level or depth.

Key Characteristics of a Full Binary Tree:

• Each non-leaf node has two children.
• The tree can be completely filled except for the leaf nodes.
• If the binary tree has $n$ nodes, it has $(n+1)\mathrm{/}2$ leaf nodes.

In comparison to other binary trees:

• A complete binary tree is not necessarily full but may have more nodes on the last level. Every level is completely filled except possibly the last one.
• A perfect binary tree is a binary tree where all nodes have two children, and all leaf nodes are at the same level, essentially a complete and full tree.

---

Properties of Full Binary Trees

1. Number of Nodes: A full binary tree with $n$ nodes will have exactly $n=2^h-1$ nodes, where $h$ is the height of the tree (height is the number of edges from the root to the deepest leaf).
2. Leaf Nodes: The number of leaf nodes $L$ in a full binary tree is given by: $$L=\frac{n+1}{2}$$ where $n$ is the total number of nodes in the tree.
3. Height of Full Binary Tree: The height of a full binary tree with $n$ nodes is $h={\log }_2(n+1)-1$.
4. Perfect Substructure: Any subtree of a full binary tree is also a full binary tree.

---

Example of a Full Binary Tree

Here’s a visual representation of a full binary tree:

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

In the tree above:

• The root node has two children (2 and 3).
• Node 2 has two children (4 and 5), and node 3 has two children (6 and 7).
• Nodes 4, 5, 6, and 7 are leaf nodes (have no children).

---

Operations on Full Binary Tree

1. Insertion in a Full Binary Tree

In a full binary tree, every non-leaf node has exactly two children. Insertion is generally performed by adding a new node as a child of the first available parent node. This method ensures the binary tree maintains its full structure.

However, since the full binary tree requires each internal node to have two children, ensuring the tree stays full while inserting can involve more complex balancing mechanisms (like in AVL trees).

For insertion in a perfectly filled binary tree, a node will be inserted at the first available position on the last level.

2. Traversing a Full Binary Tree

Traversal is a common operation where we visit all nodes of the tree in a specific order. The main types of tree traversal are:

• Preorder Traversal: Visit the root, traverse the left subtree, and traverse the right subtree.
• Inorder Traversal: Traverse the left subtree, visit the root, and traverse the right subtree.
• Postorder Traversal: Traverse the left subtree, traverse the right subtree, and visit the root.
• Level Order Traversal: Traverse the tree level by level.

3. Deletion in a Full Binary Tree

Deletion in a full binary tree involves removing the leaf node or the deepest node in the tree. If a non-leaf node is deleted, its children are promoted to maintain the tree's structure.

---

Code Example: Full Binary Tree in Python

Below is an example of implementing a Full Binary Tree in Python. The tree class supports insertion and traversal.

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.value = key

class FullBinaryTree:
    def __init__(self):
        self.root = None
    
    def insert(self, root, key):
        if root is None:
            return Node(key)
        
        # First, insert the new node in the left or right subtree
        queue = [root]
        while queue:
            temp = queue.pop(0)
            
            # If left child is None, insert the node there
            if not temp.left:
                temp.left = Node(key)
                return root
            else:
                queue.append(temp.left)
            
            # If right child is None, insert the node there
            if not temp.right:
                temp.right = Node(key)
                return root
            else:
                queue.append(temp.right)
    
    def inorder_traversal(self, root):
        if root:
            self.inorder_traversal(root.left)  # Visit left subtree
            print(root.value, end=" ")  # Visit root
            self.inorder_traversal(root.right)  # Visit right subtree

    def preorder_traversal(self, root):
        if root:
            print(root.value, end=" ")  # Visit root
            self.preorder_traversal(root.left)  # Visit left subtree
            self.preorder_traversal(root.right)  # Visit right subtree

# Example Usage
full_tree = FullBinaryTree()
full_tree.root = full_tree.insert(full_tree.root, 1)
full_tree.insert(full_tree.root, 2)
full_tree.insert(full_tree.root, 3)
full_tree.insert(full_tree.root, 4)
full_tree.insert(full_tree.root, 5)
full_tree.insert(full_tree.root, 6)
full_tree.insert(full_tree.root, 7)

print("Inorder Traversal of Full Binary Tree:")
full_tree.inorder_traversal(full_tree.root)

print("\nPreorder Traversal of Full Binary Tree:")
full_tree.preorder_traversal(full_tree.root)

Output:

Inorder Traversal of Full Binary Tree:
4 2 5 1 6 3 7 
Preorder Traversal of Full Binary Tree:
1 2 4 5 3 6 7

---

Applications of Full Binary Trees

1. Heap-based Data Structures: Full binary trees are used in binary heaps, which are specialized trees used to implement efficient priority queues. The heap property requires the tree to be full at every level except the last.
2. Expression Trees: Full binary trees are used to represent mathematical expressions, where each internal node represents an operator, and each leaf node represents an operand.
3. Game Trees: In computer game theory, full binary trees are used to represent all possible moves in a game, where each level corresponds to a new move or state of the game.

---

---