Algorithm


A complete binary tree is a special type of binary tree in which all levels are completely filled, except possibly for the last level, which is filled from left to right. In other words, every level, except possibly the last, is completely filled, and all nodes are as left as possible.

Here are some key properties of a complete binary tree:

  1. Fill from left to right: The nodes are added from left to right on each level, ensuring that the left child is filled before the right child.

  2. Last level: The last level of the tree may not be completely filled, but the nodes in that level should be filled from left to right.

  3. Height: The height of the tree is minimized, given the number of nodes. If the last level is partially filled, it is filled from left to right.

  4. Array representation: A complete binary tree can be efficiently represented using an array. If a node is at index i in the array, its left child is at index 2i+1 and its right child is at index 2i+2.

For example, consider the following complete binary tree:

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

 

In the corresponding array representation, the elements would be: [1, 2, 3, 4, 5, 6].

The concept of a complete binary tree is often used in data structures and algorithms, particularly in heap implementations, where the heap is a complete binary tree with specific ordering properties.

 

Code Examples

#1 Complete Binary Tree implement in Python

Code - Python Programming

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

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

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

    def _insert(self, current, key):
        queue = [current]
        while queue:
            node = queue.pop(0)
            if not node.left:
                node.left = Node(key)
                break
            elif not node.right:
                node.right = Node(key)
                break
            else:
                queue.append(node.left)
                queue.append(node.right)

    def level_order_traversal(self):
        if not self.root:
            return []

        result = []
        queue = [self.root]

        while queue:
            node = queue.pop(0)
            result.append(node.key)

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        return result

# Example usage:
if __name__ == "__main__":
    cbt = CompleteBinaryTree()
    keys = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    
    for key in keys:
        cbt.insert(key)

    print("Level Order Traversal:", cbt.level_order_traversal())
Copy The Code & Try With Live Editor

#2 Complete Binary Tree implement in Java

Code - Java Programming

class Node {
    int data;
    Node left, right;

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

class CompleteBinaryTree {
    Node root;

    // Constructor to create a new complete binary tree
    public CompleteBinaryTree() {
        root = null;
    }

    // Function to insert a new node in the tree
    public void insert(int key) {
        root = insert(root, key);
    }

    // Recursive function to insert a new node with the given key
    private Node insert(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }

        // Insert the new node in the level order traversal
        if (root.left == null) {
            root.left = new Node(key);
        } else if (root.right == null) {
            root.right = new Node(key);
        } else {
            // If left and right are already filled, insert in the next level
            root.left = insert(root.left, key);
        }
        return root;
    }

    // Function to perform a level order traversal of the tree
    public void levelOrderTraversal() {
        if (root == null) {
            return;
        }

        int height = getHeight(root);
        for (int i = 1; i  < = height; i++) {
            printGivenLevel(root, i);
        }
    }

    // Function to get the height of the tree
    private int getHeight(Node root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = getHeight(root.left);
            int rightHeight = getHeight(root.right);

            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

    // Function to print nodes at a given level
    private void printGivenLevel(Node root, int level) {
        if (root == null) {
            return;
        }
        if (level == 1) {
            System.out.print(root.data + " ");
        } else if (level > 1) {
            printGivenLevel(root.left, level - 1);
            printGivenLevel(root.right, level - 1);
        }
    }

    public static void main(String[] args) {
        CompleteBinaryTree tree = new CompleteBinaryTree();
        for (int i = 1; i  < = 10; i++) {
            tree.insert(i);
        }

        System.out.println("Level Order Traversal of the Complete Binary Tree:");
        tree.levelOrderTraversal();
    }
}
Copy The Code & Try With Live Editor

#3 Complete Binary Tree implement in C

Code - C Programming

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

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

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

// Function to insert a node into the tree
TreeNode* insert(TreeNode* root, int value, int index, int n) {
    // Base case: If the index is greater than or equal to n, return
    if (index >= n) {
        return root;
    }

    // Create a new node with the given value
    root = createNode(value);

    // Recursively insert the left child
    root->left = insert(root->left, 2 * index + 1, n);

    // Recursively insert the right child
    root->right = insert(root->right, 2 * index + 2, n);

    return root;
}

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

int main() {
    // Number of nodes in the tree
    int n;
    printf("Enter the number of nodes in the tree: ");
    scanf("%d", &n);

    // Initialize the root of the tree
    TreeNode* root = NULL;

    // Insert nodes into the tree
    root = insert(root, 1, 0, n);

    // Print the tree in in-order traversal
    printf("In-order traversal of the complete binary tree: ");
    inOrderTraversal(root);

    // Free the memory allocated for the tree nodes
    // (In a real-world scenario, you might want to implement a proper tree deletion function)
    return 0;
}
Copy The Code & Try With Live Editor

#4 Complete Binary Tree implement in C++

Code - C++ Programming

#include <iostream>
#include <queue>

// Define the structure of a binary tree node
template  < typename T>
struct Node {
    T data;
    Node* left;
    Node* right;

    // Constructor
    Node(T value) : data(value), left(nullptr), right(nullptr) {}
};

// Define the CompleteBinaryTree class
template  < typename T>
class CompleteBinaryTree {
private:
    Node* root;

public:
    // Constructor
    CompleteBinaryTree() : root(nullptr) {}

    // Insert a node into the tree
    void insert(T value) {
        if (root == nullptr) {
            root = new Node(value);
            return;
        }

        std::queue < Node*> q;
        q.push(root);

        while (!q.empty()) {
            Node < T>* temp = q.front();
            q.pop();

            if (!temp->left) {
                temp->left = new Node < T>(value);
                break;
            } else {
                q.push(temp->left);
            }

            if (!temp->right) {
                temp->right = new Node < T>(value);
                break;
            } else {
                q.push(temp->right);
            }
        }
    }

    // Inorder traversal
    void inorder(Node < T>* node) {
        if (node) {
            inorder(node->left);
            std::cout << node->data << " ";
            inorder(node->right);
        }
    }

    // Public method to start inorder traversal from the root
    void inorderTraversal() {
        inorder(root);
        std::cout << std::endl;
    }
};

// Example usage
int main() {
    CompleteBinaryTree < int> tree;

    // Insert elements into the tree
    tree.insert(1);
    tree.insert(2);
    tree.insert(3);
    tree.insert(4);
    tree.insert(5);

    // Perform inorder traversal
    std::cout << "Inorder Traversal: ";
    tree.inorderTraversal();

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

Demonstration


Complete Binary Tree-DevsEnv