Algorithm

A full binary tree is a type of binary tree in which every node other than the leaves has two children, and all leaf nodes are at the same level. In other words, a binary tree is considered "full" if every node has either 0 or 2 children. No node in a full binary tree has only one child.

Here are some characteristics of a full binary tree:

    1. Nodes and Levels:

      • Every level of the tree is completely filled, except possibly for the last level.
      • If the last level is not completely filled, the nodes are filled from left to right.

    2. Number of Nodes:

      • If the height of the tree is h, the number of nodes in a full binary tree is 2h+1−1.
      • Each level of the tree doubles the number of nodes in the previous level.

    3. Height and Depth:

      • The height of a full binary tree with n nodes is ⌊log⁡2(n+1)⌋.
      • The depth of the deepest node is the height of the tree.

    4. Examples:

      • Here's an example of a full binary tree with height h=2:

        markdown
            1
   / \
  2   3
 / \
4   5

  • In this example, every non-leaf node has exactly two children, and all leaf nodes are at the same level.

 

Code Examples

#1 Full Binary Tree implement in Python

Code - Python Programming

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

class FullBinaryTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        if not self.root:
            self.root = Node(key)
        else:
            self._insert(key, self.root)

    def _insert(self, key, current_node):
        if key < current_node.key:
            if current_node.left:
                self._insert(key, current_node.left)
            else:
                current_node.left = Node(key)
        else:
            if current_node.right:
                self._insert(key, current_node.right)
            else:
                current_node.right = Node(key)

    def is_full(self):
        return self._is_full(self.root)

    def _is_full(self, node):
        if not node:
            return True
        if not node.left and not node.right:
            return True
        if node.left and node.right:
            return self._is_full(node.left) and self._is_full(node.right)
        return False

# Example usage:
tree = FullBinaryTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(2)
tree.insert(4)
tree.insert(6)
tree.insert(8)

print("Is the tree full?", tree.is_full())
Copy The Code & Try With Live Editor

#2 Full Binary Tree implement in Java

Code - Java Programming

class Node {
    int data;
    Node left, right;

    public Node(int item) {
        data = item;
        left = right = null;
    }
}

public class FullBinaryTree {
    Node root;

    // Method to insert a new node
    private Node insert(Node root, int data) {
        if (root == null) {
            return new Node(data);
        }

        if (data  <  root.data) {
            root.left = insert(root.left, data);
        } else if (data > root.data) {
            root.right = insert(root.right, data);
        }

        return root;
    }

    // Method to check if the binary tree is full
    private boolean isFull(Node root) {
        if (root == null) {
            return true;
        }

        // If a node has only one child, it's not a full binary tree
        if ((root.left == null && root.right != null) || (root.left != null && root.right == null)) {
            return false;
        }

        // Recursively check the left and right subtrees
        return isFull(root.left) && isFull(root.right);
    }

    // Wrapper method to check if the binary tree is full
    public boolean isFullBinaryTree() {
        return isFull(root);
    }

    public static void main(String[] args) {
        FullBinaryTree tree = new FullBinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        if (tree.isFullBinaryTree()) {
            System.out.println("The binary tree is full.");
        } else {
            System.out.println("The binary tree is not full.");
        }
    }
}
Copy The Code & Try With Live Editor

#3 Full Binary Tree implement in C

Code - C Programming

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

// Define the structure for a tree node
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Function to create a new node with the given data
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// Function to insert a new node into the tree
Node* insert(Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }

    // Insert in left subtree if data is less than the current node
    if (data  <  root->data) {
        root->left = insert(root->left, data);
    }
    // Insert in right subtree if data is greater than or equal to the current node
    else {
        root->right = insert(root->right, data);
    }

    return root;
}

// Function to print the tree in-order
void inOrderTraversal(Node* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);
        printf("%d ", root->data);
        inOrderTraversal(root->right);
    }
}

// Function to free the memory allocated for the tree nodes
void freeTree(Node* root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

int main() {
    Node* root = NULL;

    // Insert some nodes into the tree
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    // Print the tree in-order
    printf("In-order traversal: ");
    inOrderTraversal(root);
    printf("\n");

    // Free the memory allocated for the tree nodes
    freeTree(root);

    return 0;
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration

Full Binary Tree-DevsEnv