Full Binary Tree

What is a Full Binary Tree?

A full binary tree is a specific type of binary tree where every node has either zero or two children. This means no node in a full binary tree can have only one child. If a node has children, it must have both a left & a right child. This property makes full binary trees very predictable & structured, which can be particularly useful in certain types of algorithms & data processes.

For example, in binary search trees (a common application of binary trees), having the structure of a full binary tree can make the tree more balanced & therefore improve the efficiency of search operations. Here is how a full binary tree looks in a simple representation:

In this tree, every node that has children has two children (like the node with value 8 has two children, 3 & 10). Node 10, which has only one child in this example, would not satisfy the conditions of a full binary tree if it did not have a left child as well.

Examples

• C
• C++
• Java
• Python

C

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* newNode(int key) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = key;
    node->left = node->right = NULL;
    return node;
}

int isFullBinaryTree(struct TreeNode* node) {
    if (node == NULL)
        return 1;
    if (node->left == NULL && node->right == NULL)
        return 1;
    if (node->left != NULL && node->right != NULL)
        return isFullBinaryTree(node->left) && isFullBinaryTree(node->right);
    return 0;
}

int main() {
    struct TreeNode* root = newNode(8);
    root->left = newNode(3);
    root->right = newNode(10);
    root->left->left = newNode(1);
    root->left->right = newNode(6);
    root->right->right = newNode(14);

    printf("Is the tree a full binary tree? %s\n", isFullBinaryTree(root) ? "True" : "False");

    return 0;
}

You can also try this code with Online C Compiler

Run Code

C++

#include <iostream>
using namespace std;

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int key) {
        val = key;
        left = right = nullptr;
    }
};

bool isFullBinaryTree(TreeNode* node) {
    if (node == nullptr)
        return true;
    if (node->left == nullptr && node->right == nullptr)
        return true;
    if (node->left != nullptr && node->right != nullptr)
        return isFullBinaryTree(node->left) && isFullBinaryTree(node->right);
    return false;
}

int main() {
    TreeNode* root = new TreeNode(8);
    root->left = new TreeNode(3);
    root->right = new TreeNode(10);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(6);
    root->right->right = new TreeNode(14);

    cout << "Is the tree a full binary tree? " << (isFullBinaryTree(root) ? "True" : "False") << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java

class TreeNode {
    int val;
    TreeNode left, right;

    TreeNode(int key) {
        val = key;
        left = right = null;
    }
}

public class Main {
    public static boolean isFullBinaryTree(TreeNode node) {
        if (node == null)
            return true;
        if (node.left == null && node.right == null)
            return true;
        if (node.left != null && node.right != null)
            return isFullBinaryTree(node.left) && isFullBinaryTree(node.right);
        return false;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(3);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(6);
        root.right.right = new TreeNode(14);

        System.out.println("Is the tree a full binary tree? " + (isFullBinaryTree(root) ? "True" : "False"));
    }
}

You can also try this code with Online Java Compiler

Run Code

Python

class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def is_full_binary_tree(node):
    if node is None:
        return True
    if node.left is None and node.right is None:  
        return True
    if node.left is not None and node.right is not None:  
        return is_full_binary_tree(node.left) and is_full_binary_tree(node.right) 
    return False
# Example tree
root = TreeNode(8)
root.left = TreeNode(3)
root.right = TreeNode(10)
root.left.left = TreeNode(1)
root.left.right = TreeNode(6)
root.right.right = TreeNode(14)
print("Is the tree a full binary tree?", is_full_binary_tree(root))

You can also try this code with Online Python Compiler

Run Code

Output

Is the tree a full binary tree? False

This function is_full_binary_tree checks each node to ensure that if it has children, it has both left & right children. It recursively checks this condition for all nodes to ensure the entire tree conforms to the definition of a full binary tree.

Full Binary Tree Theorem

The Full Binary Tree Theorem provides a key insight into the structure & properties of full binary trees. It states that if a full binary tree has 

n leaves (also known as terminal nodes, which are nodes without any children), then it must have 2n−1 nodes in total. This relationship is crucial because it helps in understanding the efficiency & balance of full binary trees.

Here's why this theorem is useful:

• Predictability: It allows us to predict the number of nodes & the depth of the tree if we know the number of leaves. This can be particularly helpful during the design of algorithms that need to process these trees efficiently.
   
• Efficiency in storage: Knowing the exact number of nodes and their arrangement helps in optimizing memory allocation.
   

To visualize how this theorem works in practice, let's consider a full binary tree with 4 leaves. According to the theorem, such a tree would have 

2×4−1=7 nodes in total.

Here’s a practical example in Python to illustrate a tree construction & to validate the theorem:

• Python

Python

class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def count_nodes(root):
    if root is None:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

def count_leaves(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:  
        return 1
    return count_leaves(root.left) + count_leaves(root.right)

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(2)
root.left.right = TreeNode(8)
root.right.left = TreeNode(12)
root.right.right = TreeNode(20)

total_nodes = count_nodes(root)
total_leaves = count_leaves(root)

print("Total nodes:", total_nodes)
print("Total leaves:", total_leaves)
print("Does the theorem hold?", total_nodes == 2 * total_leaves - 1)

You can also try this code with Online Python Compiler

Run Code

Output

Total nodes: 7
Total leaves: 4
Does the theorem hold? True

This code defines functions to count the total nodes & leaves in a tree & checks whether the theorem holds true for a manually constructed full binary tree.

Facts Derived from the Theorem

The Full Binary Tree Theorem isn't just a mathematical curiosity; it has practical implications that can be extremely useful in computer science, especially in areas like algorithm design & data structure optimization. Here are some key facts derived from the theorem that underscore its utility:

• Balance and Depth: The theorem ensures that full binary trees are automatically balanced. A balanced tree means that the nodes are spread across the tree in such a way that the distance from the root to any leaf is minimized, compared to other structures. This balance results in a lower tree height, making operations like search, insert, and delete faster.
   
• Memory Efficiency: With the predictable structure of full binary trees, memory allocation becomes more straightforward and can be optimized. Knowing the exact number of nodes helps in pre-allocating memory, thus improving the performance of the applications using these trees.
   
• Simplified Coding: When programmers know they are working with a full binary tree, the coding for tree traversal (like pre-order, in-order, and post-order) can be simplified. This is because there’s no need to check for missing children continually.
   

Let's illustrate the balance property with a simple Python example:

def tree_depth(root):
    if root is None:
        return 0
    else:
        left_depth = tree_depth(root.left)
        right_depth = tree_depth(root.right)
        return max(left_depth, right_depth) + 1
# Using the same full binary tree from the previous example
depth = tree_depth(root)
print("Depth of the tree:", depth)

This function calculates the depth of the tree, which represents the longest path from the root to the furthest leaf. In a full binary tree, this depth is minimized compared to less organized structures, demonstrating the tree's balanced nature.

Frequently Asked Questions

What is full binary tree proofs?

Full binary tree proofs involve demonstrating that, in a binary tree where each node has 0 or 2 children, specific structural properties hold.

How many nodes are in a full binary tree?

A full binary tree with nnn internal nodes has 2n+1 total nodes, ensuring a balanced structure with all levels fully filled.

Why are full binary trees important in computer science?

Full binary trees are essential because they provide efficient data organization for quick search, insert, and delete operations due to their balanced nature, making them ideal for various applications, including binary search trees and heap data structures.

How does the full binary tree theorem assist in memory allocation?

The theorem predicts the total number of nodes based on the number of leaves, allowing for precise memory allocation, which enhances the efficiency of data operations and storage within the tree.

Can a full binary tree be used in real-world applications?

Yes, full binary trees are widely used in real-world applications, particularly in scenarios requiring efficient, organized data access, such as database indexing and network routing algorithms.

Conclusion

In this article, we have learned about full binary trees, starting from the basic concept of binary trees to understanding what distinguishes a full binary tree with its specific properties. We explored the Full Binary Tree Theorem, which shows the relationship between the number of leaves and the total nodes, and discussed practical implications that impact coding and data structure design. 

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure andAlgorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.