Types of Binary Trees Based on the Number of Children

Full Binary Tree

A Full Binary Tree is a binary tree in which every node other than the leaves has two children. These trees are balanced, and they have a fixed structure, which makes them easier to manage and traverse.

Space Complexity: O(n)
Time Complexity: O(n) for traversal


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

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

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

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

# Example Usage
tree = FullBinaryTree()
for i in range(7):
    tree.insert(i + 1)
print("Inorder:", tree.inorder(tree.root))

Degenerate Binary Tree

A Degenerate Binary Tree is a tree where each parent node has only one child, resembling a linked list. It is a pathological case where the performance of the tree operations degrades to that of a linear structure.

Space Complexity: O(n)
Time Complexity: O(n) for traversal


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

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

    def insert(self, data):
        if self.root is None:
            self.root = Node(data)
        else:
            current = self.root
            while current.right is not None:
                current = current.right
            current.right = Node(data)

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

# Example Usage
tree = DegenerateBinaryTree()
for i in range(7):
    tree.insert(i + 1)
print("Inorder:", tree.inorder(tree.root))

Skewed Binary Tree

A Skewed Binary Tree is a binary tree where all the nodes are either on the left side or the right side. It can be either left-skewed or right-skewed based on the side where the nodes are added.

Space Complexity: O(n)
Time Complexity: O(n) for traversal


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

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

    def insert(self, data, skew='right'):
        if self.root is None:
            self.root = Node(data)
        else:
            current = self.root
            if skew == 'right':
                while current.right is not None:
                    current = current.right
                current.right = Node(data)
            elif skew == 'left':
                while current.left is not None:
                    current = current.left
                current.left = Node(data)

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

# Example Usage
tree = SkewedBinaryTree()
for i in range(7):
    tree.insert(i + 1, skew='right')
print("Inorder:", tree.inorder(tree.root))