Types of Binary Tree Based on the Completion of Levels

Complete Binary Tree

A Complete Binary Tree is a binary tree where all levels, except possibly the last, are completely filled, and all nodes are as far left as possible.


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

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

    def insert(self, data):
        new_node = Node(data)
        if not self.root:
            self.root = new_node
        else:
            queue = [self.root]
            while queue:
                node = queue.pop(0)
                if not node.left:
                    node.left = new_node
                    break
                else:
                    queue.append(node.left)
                if not node.right:
                    node.right = new_node
                    break
                else:
                    queue.append(node.right)

    def inorder(self, node):
        result = []
        if node:
            result = self.inorder(node.left)
            result.append(node.data)
            result = result + self.inorder(node.right)
        return result

    def display_traversal(self):
        return ' -> '.join(map(str, self.inorder(self.root)))

# Example Usage
cbt = CompleteBinaryTree()
for i in range(1, 8):
    cbt.insert(i)
print(cbt.display_traversal())

Perfect Binary Tree

A Perfect Binary Tree is a binary tree where all the internal nodes have two children, and all leaves are at the same level.


class Node:
    def __init__(self, data: int):
        self.data = data
        self.left: Node | None = None
        self.right: Node | None = None

class PerfectBinaryTree:
    def __init__(self):
        self.root: Node | None = None

    def insert_level_order(self, arr: list[int], i: int = 0) -> Node | None:
        if i >= len(arr):
            return None

        node = Node(arr[i])
        node.left = self.insert_level_order(arr, 2 * i + 1)
        node.right = self.insert_level_order(arr, 2 * i + 2)

        return node

    def build_tree(self, arr: list[int]) -> None:
        self.root = self.insert_level_order(arr)

    def inorder(self, node: Node | None) -> list[int]:
        if not node:
            return []
        left_traversal = self.inorder(node.left)
        right_traversal = self.inorder(node.right)
        return left_traversal + [node.data] + right_traversal

    def display_traversal(self) -> str:
        if not self.root:
            return 'Tree is empty'
        return ' -> '.join(map(str, self.inorder(self.root)))

if __name__ == "__main__":
    tree = PerfectBinaryTree()
    tree.build_tree([1, 2, 3, 4, 5, 6, 7])
    print(tree.display_traversal())  # Output: 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7

Balanced Binary Tree

A Balanced Binary Tree is a binary tree in which the height of the left and right subtrees of any node differ by at most one.


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

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

    def insert(self, data):
        self.root = self._insert(self.root, data)

    def _insert(self, node, data):
        if node is None:
            return Node(data)
        if data < node.data:
            node.left = self._insert(node.left, data)
        else:
            node.right = self._insert(node.right, data)
        return node

    def inorder(self, node):
        result = []
        if node:
            result = self.inorder(node.left)
            result.append(node.data)
            result = result + self.inorder(node.right)
        return result

    def display_traversal(self):
        return ' -> '.join(map(str, self.inorder(self.root)))

# Example Usage
bbt = BalancedBinaryTree()
for num in [30, 20, 40, 10, 25, 35, 50]:
    bbt.insert(num)
print(bbt.display_traversal())