Binary Tree

A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child. This implementation provides a general-purpose binary tree with comprehensive operations for construction, traversal, and manipulation.

Features

Hierarchical structure - nodes organized in parent-child relationships
Flexible insertion - insert nodes as left or right children
Multiple traversals - inorder, preorder, postorder, and level-order
Tree properties - height, size, balance checking, diameter calculation
Search operations - find nodes and check existence
Tree manipulation - mirroring, comparison, deletion
Type safe - generic implementation with type checking
Utility operations - leaf collection, tree validation

Time Complexities

Operation	Average Case	Worst Case	Description
Search	O(log n)	O(n)	Find node by value
Insert	O(log n)	O(n)	Add new node
Delete	O(log n)	O(n)	Remove node
Traversal	O(n)	O(n)	Visit all nodes
Height	O(n)	O(n)	Calculate tree height
Size	O(1)	O(1)	Get number of nodes
Balance Check	O(n)	O(n)	Verify if balanced
Mirror	O(n)	O(n)	Reverse tree structure
Diameter	O(n)	O(n)	Find longest path

Space Complexity: O(n) for storage, O(h) for recursion stack where h is height

Basic Usage

Creating and Initializing

from algo.data_structs.trees.binary_tree import BinaryTree, TreeNode

# Create empty tree
tree = BinaryTree()
print(tree.is_empty())     # True
print(tree.size())         # 0
print(tree.height())       # -1

# Create tree with root node
tree = BinaryTree(10)
print(tree.is_empty())     # False
print(tree.size())         # 1
print(tree.height())       # 0
print(tree.root.data)      # 10

# Tree is generic - can specify type
int_tree = BinaryTree[int](42)
str_tree = BinaryTree[str]("root")

Creating Nodes

# Create individual nodes
node = TreeNode(5)
print(node.data)           # 5
print(node.left)           # None
print(node.right)          # None

# Create node with children
left_child = TreeNode(3)
right_child = TreeNode(7)
parent = TreeNode(5, left_child, right_child)

print(parent.data)         # 5
print(parent.left.data)    # 3
print(parent.right.data)   # 7

# Check node properties
print(node.is_leaf())      # True
print(parent.is_leaf())    # False
print(parent.has_both_children())  # True

Building Trees

# Build tree step by step
tree = BinaryTree(1)

# Insert left and right children
tree.insert_left(1, 2)    # Insert 2 as left child of 1
tree.insert_right(1, 3)   # Insert 3 as right child of 1

print(tree.size())         # 3
print(tree.height())       # 1

# Insert more nodes
tree.insert_left(2, 4)    # Insert 4 as left child of 2
tree.insert_right(2, 5)   # Insert 5 as right child of 2

print(tree.size())         # 5
print(tree.height())       # 2

# Tree structure:
#       1
#      / \
#     2   3
#    / \
#   4   5

Handling Existing Children

tree = BinaryTree(1)
tree.insert_left(1, 2)

# When inserting where child already exists, existing child becomes child of new node
tree.insert_left(1, 3)    # 3 becomes new left child, 2 becomes left child of 3

print(tree.root.left.data)         # 3
print(tree.root.left.left.data)    # 2

# Tree structure:
#   1
#  /
# 3
#/
#2

Tree Traversals

Inorder Traversal (Left-Root-Right)

tree = BinaryTree(1)
tree.insert_left(1, 2)
tree.insert_right(1, 3)
tree.insert_left(2, 4)
tree.insert_right(2, 5)

# Inorder: left subtree, root, right subtree
result = tree.inorder_traversal()
print(result)              # [4, 2, 5, 1, 3]

# Common use: Get sorted order in BST

Preorder Traversal (Root-Left-Right)

# Preorder: root, left subtree, right subtree
result = tree.preorder_traversal()
print(result)              # [1, 2, 4, 5, 3]

# Common use: Tree serialization, expression trees

Postorder Traversal (Left-Right-Root)

# Postorder: left subtree, right subtree, root
result = tree.postorder_traversal()
print(result)              # [4, 5, 2, 3, 1]

# Common use: Tree deletion, calculating directory sizes

Level-order Traversal (Breadth-First)

# Level-order: visit nodes level by level
result = tree.level_order_traversal()
print(result)              # [1, 2, 3, 4, 5]

# Common use: Tree serialization, finding shortest path

Traversal Comparisons

# Different traversals for same tree
tree = BinaryTree("A")
tree.insert_left("A", "B")
tree.insert_right("A", "C")
tree.insert_left("B", "D")
tree.insert_right("B", "E")

print("Inorder:   ", tree.inorder_traversal())    # ['D', 'B', 'E', 'A', 'C']
print("Preorder:  ", tree.preorder_traversal())   # ['A', 'B', 'D', 'E', 'C']
print("Postorder: ", tree.postorder_traversal())  # ['D', 'E', 'B', 'C', 'A']
print("Level-order:", tree.level_order_traversal()) # ['A', 'B', 'C', 'D', 'E']

Search Operations

Finding Nodes

tree = BinaryTree(10)
tree.insert_left(10, 5)
tree.insert_right(10, 15)
tree.insert_left(5, 3)
tree.insert_right(5, 7)

# Check if values exist
print(tree.find(10))       # True
print(tree.find(5))        # True
print(tree.find(99))       # False

# Search works with any data type
str_tree = BinaryTree("root")
str_tree.insert_left("root", "left")
str_tree.insert_right("root", "right")

print(str_tree.find("left"))   # True
print(str_tree.find("missing")) # False

Working with Empty Trees

empty_tree = BinaryTree()

# All operations handle empty trees gracefully
print(empty_tree.find(42))     # False
print(empty_tree.inorder_traversal())   # []
print(empty_tree.get_leaves())          # []
print(empty_tree.is_balanced())         # True (empty tree is balanced)

Tree Properties

Size and Height

tree = BinaryTree(1)
tree.insert_left(1, 2)
tree.insert_right(1, 3)
tree.insert_left(2, 4)

print(f"Size: {tree.size()}")      # Size: 4
print(f"Height: {tree.height()}")  # Height: 2

# Height is number of edges from root to deepest leaf
# Empty tree has height -1, single node has height 0

Leaf Nodes

# Get all leaf nodes (nodes with no children)
leaves = tree.get_leaves()
print(f"Leaves: {leaves}")         # Leaves: [4, 3]

# Leaves are collected in traversal order

Balance Checking

# Check if tree is height-balanced
# (heights of subtrees differ by at most 1)

# Balanced tree
balanced_tree = BinaryTree(1)
balanced_tree.insert_left(1, 2)
balanced_tree.insert_right(1, 3)
print(balanced_tree.is_balanced())  # True

# Unbalanced tree (like a linked list)
unbalanced_tree = BinaryTree(1)
unbalanced_tree.insert_left(1, 2)
unbalanced_tree.insert_left(2, 3)
unbalanced_tree.insert_left(3, 4)
print(unbalanced_tree.is_balanced())  # False

Diameter Calculation

# Diameter is longest path between any two nodes
tree = BinaryTree(1)
tree.insert_left(1, 2)
tree.insert_right(1, 3)
tree.insert_left(2, 4)
tree.insert_right(2, 5)

diameter = tree.diameter()
print(f"Diameter: {diameter}")     # Diameter: 4
# Path: 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3)

Tree Manipulation

Mirroring Trees

tree = BinaryTree(1)
tree.insert_left(1, 2)
tree.insert_right(1, 3)
tree.insert_left(2, 4)
tree.insert_right(2, 5)

print("Original inorder:", tree.inorder_traversal())  # [4, 2, 5, 1, 3]

# Mirror the tree (swap all left and right children)
tree.mirror()
print("Mirrored inorder:", tree.inorder_traversal())  # [3, 1, 5, 2, 4]

# Mirror again to restore
tree.mirror()
print("Restored inorder:", tree.inorder_traversal())  # [4, 2, 5, 1, 3]

Tree Comparison

# Create two identical trees
tree1 = BinaryTree(1)
tree1.insert_left(1, 2)
tree1.insert_right(1, 3)

tree2 = BinaryTree(1)
tree2.insert_left(1, 2)
tree2.insert_right(1, 3)

print(tree1.are_identical(tree2))  # True

# Modify one tree
tree2.insert_left(2, 4)
print(tree1.are_identical(tree2))  # False

# Empty trees are identical
empty1 = BinaryTree()
empty2 = BinaryTree()
print(empty1.are_identical(empty2))  # True

Node Deletion

tree = BinaryTree(10)
tree.insert_left(10, 5)
tree.insert_right(10, 15)
tree.insert_left(5, 3)
tree.insert_right(5, 7)

print(f"Size before: {tree.size()}")  # Size before: 5

# Delete leaf node
success = tree.delete(3)
print(f"Deleted 3: {success}")        # Deleted 3: True
print(f"Size after: {tree.size()}")   # Size after: 4
print(tree.find(3))                   # False

# Delete node with children (uses inorder successor)
tree.delete(5)
print(f"Size after deleting 5: {tree.size()}")

# Try to delete non-existent node
success = tree.delete(99)
print(f"Deleted 99: {success}")       # Deleted 99: False

Working with Different Types

String Trees

# Tree with string data
str_tree = BinaryTree("root")
str_tree.insert_left("root", "left")
str_tree.insert_right("root", "right")
str_tree.insert_left("left", "deep")

print(str_tree.inorder_traversal())   # ['deep', 'left', 'root', 'right']
print(str_tree.find("deep"))          # True
print(str_tree.height())              # 2

Numeric Trees

# Tree with mixed numeric types
num_tree = BinaryTree(1.0)
num_tree.insert_left(1.0, 2)
num_tree.insert_right(1.0, 3.14)

print(num_tree.inorder_traversal())   # [2, 1.0, 3.14]
print(num_tree.find(3.14))            # True

Custom Object Trees

class Person:
    def __init__(self, name: str, age: int):
        self.name = name
        self.age = age

    def __eq__(self, other):
        return isinstance(other, Person) and self.name == other.name and self.age == other.age

    def __str__(self):
        return f"{self.name}({self.age})"

# Tree with custom objects
alice = Person("Alice", 30)
bob = Person("Bob", 25)
charlie = Person("Charlie", 35)

person_tree = BinaryTree(alice)
person_tree.insert_left(alice, bob)
person_tree.insert_right(alice, charlie)

print(person_tree.find(bob))          # True
print(person_tree.size())             # 3

# Traversal returns objects
people = person_tree.inorder_traversal()
for person in people:
    print(person)  # Bob(25), Alice(30), Charlie(35)

Tree Display and Debugging

String Representation

# Empty tree
empty_tree = BinaryTree()
print(str(empty_tree))     # Empty Tree

# Single node tree
single_tree = BinaryTree(42)
print(single_tree)
# Root: 42

# Multi-level tree
tree = BinaryTree(1)
tree.insert_left(1, 2)
tree.insert_right(1, 3)
tree.insert_left(2, 4)

print(tree)
# Root: 1
#   L--- 2
#     L--- 4
#     R--- None
#   R--- 3

# Detailed representation for debugging
print(repr(tree))          # BinaryTree(size=4, height=2, root=TreeNode(1))

Tree Visualization

def print_tree_info(tree, name="Tree"):
    """Print comprehensive tree information."""
    print(f"\n{name} Information:")
    print(f"  Size: {tree.size()}")
    print(f"  Height: {tree.height()}")
    print(f"  Is empty: {tree.is_empty()}")
    print(f"  Is balanced: {tree.is_balanced()}")
    print(f"  Diameter: {tree.diameter()}")
    print(f"  Leaves: {tree.get_leaves()}")
    print(f"  Inorder: {tree.inorder_traversal()}")
    print(f"  Level-order: {tree.level_order_traversal()}")

# Example usage
tree = BinaryTree(10)
tree.insert_left(10, 5)
tree.insert_right(10, 15)
tree.insert_left(5, 3)
tree.insert_right(15, 20)

print_tree_info(tree, "Sample Binary Tree")

Error Handling

# Operations on empty tree
empty_tree = BinaryTree()

# Safe operations
print(empty_tree.is_empty())           # True
print(empty_tree.size())               # 0
print(empty_tree.height())             # -1
print(empty_tree.find(42))             # False
print(empty_tree.inorder_traversal())  # []

# Insertion operations that fail gracefully
print(empty_tree.insert_left(1, 2))    # False (no parent with value 1)
print(empty_tree.insert_right(1, 3))   # False

# Deletion operations
print(empty_tree.delete(42))           # False

# Operations with non-existent parents
tree = BinaryTree(1)
print(tree.insert_left(99, 2))         # False (no node with value 99)
print(tree.insert_right(99, 3))        # False

Common Patterns

Building from Lists

def build_complete_tree(values):
    """Build a complete binary tree from a list of values."""
    if not values:
        return BinaryTree()

    tree = BinaryTree(values[0])

    # Use level-order insertion for complete tree
    from collections import deque
    queue = deque([(tree.root, 0)])  # (node, index)

    while queue:
        node, index = queue.popleft()

        left_index = 2 * index + 1
        right_index = 2 * index + 2

        if left_index < len(values):
            left_child = TreeNode(values[left_index])
            node.left = left_child
            queue.append((left_child, left_index))

        if right_index < len(values):
            right_child = TreeNode(values[right_index])
            node.right = right_child
            queue.append((right_child, right_index))

    return tree

# Build complete tree from list
values = [1, 2, 3, 4, 5, 6, 7]
complete_tree = build_complete_tree(values)
print(complete_tree.level_order_traversal())  # [1, 2, 3, 4, 5, 6, 7]

Tree Serialization

def serialize_tree(tree):
    """Serialize tree to list using preorder traversal."""
    def serialize_node(node):
        if node is None:
            return [None]
        return [node.data] + serialize_node(node.left) + serialize_node(node.right)

    return serialize_node(tree.root)

def deserialize_tree(data):
    """Deserialize list back to tree."""
    def deserialize_node():
        val = next(iterator)
        if val is None:
            return None
        node = TreeNode(val)
        node.left = deserialize_node()
        node.right = deserialize_node()
        return node

    iterator = iter(data)
    root = deserialize_node()
    tree = BinaryTree()
    tree.root = root
    # Note: Would need to update size manually or recalculate
    return tree

# Example usage
tree = BinaryTree(1)
tree.insert_left(1, 2)
tree.insert_right(1, 3)
tree.insert_left(2, 4)

serialized = serialize_tree(tree)
print(f"Serialized: {serialized}")

# Deserialize back
restored_tree = deserialize_tree(serialized)
print(f"Restored: {restored_tree.preorder_traversal()}")

Tree Validation

def validate_binary_tree(tree):
    """Validate binary tree structure and properties."""
    issues = []

    if tree.is_empty():
        return ["Tree is empty - no validation needed"]

    # Check size consistency
    def count_nodes(node):
        if node is None:
            return 0
        return 1 + count_nodes(node.left) + count_nodes(node.right)

    actual_size = count_nodes(tree.root)
    if actual_size != tree.size():
        issues.append(f"Size mismatch: reported {tree.size()}, actual {actual_size}")

    # Check for cycles (shouldn't exist in proper tree)
    visited = set()
    def check_cycles(node):
        if node is None:
            return False
        if id(node) in visited:
            return True
        visited.add(id(node))
        return check_cycles(node.left) or check_cycles(node.right)

    if check_cycles(tree.root):
        issues.append("Cycle detected in tree structure")

    # Check balance factor
    if not tree.is_balanced():
        issues.append("Tree is not height-balanced")

    return issues if issues else ["Tree structure is valid"]

# Validate a tree
tree = BinaryTree(10)
tree.insert_left(10, 5)
tree.insert_right(10, 15)

validation_results = validate_binary_tree(tree)
for result in validation_results:
    print(result)

Practical Applications

Expression Trees

class ExpressionTree(BinaryTree):
    """Binary tree for mathematical expressions."""

    def __init__(self, expression=None):
        super().__init__(expression)

    def evaluate(self):
        """Evaluate the expression tree."""
        return self._evaluate_node(self.root)

    def _evaluate_node(self, node):
        if node is None:
            return 0

        # If leaf node, return the number
        if node.is_leaf():
            return float(node.data)

        # Evaluate left and right subtrees
        left_val = self._evaluate_node(node.left)
        right_val = self._evaluate_node(node.right)

        # Apply operator
        if node.data == '+':
            return left_val + right_val
        elif node.data == '-':
            return left_val - right_val
        elif node.data == '*':
            return left_val * right_val
        elif node.data == '/':
            return left_val / right_val if right_val != 0 else float('inf')

        return 0

# Build expression tree for: (3 + 4) * (5 - 2)
expr_tree = ExpressionTree('*')
expr_tree.insert_left('*', '+')
expr_tree.insert_right('*', '-')
expr_tree.insert_left('+', '3')
expr_tree.insert_right('+', '4')
expr_tree.insert_left('-', '5')
expr_tree.insert_right('-', '2')

result = expr_tree.evaluate()
print(f"Expression result: {result}")  # 21.0

# Print the expression in infix notation
def infix_expression(tree):
    def infix_node(node):
        if node is None:
            return ""
        if node.is_leaf():
            return str(node.data)
        left = infix_node(node.left)
        right = infix_node(node.right)
        return f"({left} {node.data} {right})"

    return infix_node(tree.root)

print(f"Expression: {infix_expression(expr_tree)}")  # ((3 + 4) * (5 - 2))

Decision Trees

class DecisionTree(BinaryTree):
    """Simple decision tree for classification."""

    def __init__(self, question=None):
        super().__init__(question)

    def classify(self, data):
        """Classify data point using decision tree."""
        return self._classify_node(self.root, data)

    def _classify_node(self, node, data):
        if node is None:
            return "Unknown"

        # If leaf node, return the classification
        if node.is_leaf():
            return node.data

        # Otherwise, evaluate the condition and go left or right
        condition = node.data
        if self._evaluate_condition(condition, data):
            return self._classify_node(node.left, data)
        else:
            return self._classify_node(node.right, data)

    def _evaluate_condition(self, condition, data):
        """Simple condition evaluation."""
        # This would be more sophisticated in a real implementation
        if "age >= 18" in condition:
            return data.get("age", 0) >= 18
        elif "income > 50000" in condition:
            return data.get("income", 0) > 50000
        return False

# Build decision tree for loan approval
decision_tree = DecisionTree("age >= 18")
decision_tree.insert_left("age >= 18", "income > 50000")
decision_tree.insert_right("age >= 18", "Not Eligible")
decision_tree.insert_left("income > 50000", "Approved")
decision_tree.insert_right("income > 50000", "Needs Guarantor")

# Test classification
applicant1 = {"age": 25, "income": 60000}
applicant2 = {"age": 16, "income": 30000}
applicant3 = {"age": 30, "income": 40000}

print(f"Applicant 1: {decision_tree.classify(applicant1)}")  # Approved
print(f"Applicant 2: {decision_tree.classify(applicant2)}")  # Not Eligible
print(f"Applicant 3: {decision_tree.classify(applicant3)}")  # Needs Guarantor

File System Representation

class FileSystemTree(BinaryTree):
    """Represent file system structure as binary tree."""

    def __init__(self, name=None, is_directory=True):
        super().__init__({"name": name, "is_directory": is_directory})

    def add_file(self, parent_name, file_name, is_directory=False):
        """Add a file or directory to the tree."""
        parent_node = self._find_by_name(parent_name)
        if parent_node and parent_node.data["is_directory"]:
            file_data = {"name": file_name, "is_directory": is_directory}

            # Simple insertion logic - left for directories, right for files
            if is_directory:
                if parent_node.left is None:
                    parent_node.left = TreeNode(file_data)
                else:
                    # Find rightmost position in left subtree
                    current = parent_node.left
                    while current.right is not None:
                        current = current.right
                    current.right = TreeNode(file_data)
            else:
                if parent_node.right is None:
                    parent_node.right = TreeNode(file_data)
                else:
                    # Find rightmost position in right subtree
                    current = parent_node.right
                    while current.right is not None:
                        current = current.right
                    current.right = TreeNode(file_data)
            return True
        return False

    def _find_by_name(self, name):
        """Find node by file/directory name."""
        def search_node(node):
            if node is None:
                return None
            if node.data["name"] == name:
                return node
            left_result = search_node(node.left)
            if left_result:
                return left_result
            return search_node(node.right)

        return search_node(self.root)

    def list_contents(self, directory_name):
        """List contents of a directory."""
        dir_node = self._find_by_name(directory_name)
        if dir_node and dir_node.data["is_directory"]:
            contents = []

            # Collect from left subtree (directories)
            if dir_node.left:
                self._collect_children(dir_node.left, contents)

            # Collect from right subtree (files)
            if dir_node.right:
                self._collect_children(dir_node.right, contents)

            return contents
        return []

    def _collect_children(self, node, contents):
        """Collect immediate children names."""
        if node:
            contents.append(node.data["name"])
            # Also collect siblings
            if node.right:
                self._collect_children(node.right, contents)

# Build file system tree
fs_tree = FileSystemTree("root", True)
fs_tree.add_file("root", "documents", True)
fs_tree.add_file("root", "config.txt", False)
fs_tree.add_file("documents", "projects", True)
fs_tree.add_file("documents", "readme.md", False)

# List directory contents
print("Root contents:", fs_tree.list_contents("root"))
print("Documents contents:", fs_tree.list_contents("documents"))

Huffman Coding Tree

import heapq
from collections import defaultdict, Counter

class HuffmanNode:
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right

    def __lt__(self, other):
        return self.freq < other.freq

class HuffmanTree(BinaryTree):
    """Huffman coding tree for text compression."""

    def __init__(self, text=""):
        super().__init__()
        if text:
            self.build_from_text(text)

    def build_from_text(self, text):
        """Build Huffman tree from text."""
        # Count character frequencies
        freq_map = Counter(text)

        # Create leaf nodes for each character
        heap = [HuffmanNode(char, freq) for char, freq in freq_map.items()]
        heapq.heapify(heap)

        # Build tree bottom-up
        while len(heap) > 1:
            left = heapq.heappop(heap)
            right = heapq.heappop(heap)

            merged = HuffmanNode(
                char=None,  # Internal nodes have no character
                freq=left.freq + right.freq,
                left=left,
                right=right
            )

            heapq.heappush(heap, merged)

        # Set root
        if heap:
            self.root = heap[0]

    def generate_codes(self):
        """Generate Huffman codes for each character."""
        codes = {}

        def generate_node_codes(node, code=""):
            if node:
                if node.char is not None:  # Leaf node
                    codes[node.char] = code if code else "0"  # Single char case
                else:  # Internal node
                    generate_node_codes(node.left, code + "0")
                    generate_node_codes(node.right, code + "1")

        generate_node_codes(self.root)
        return codes

    def encode(self, text):
        """Encode text using Huffman codes."""
        codes = self.generate_codes()
        return ''.join(codes[char] for char in text)

    def decode(self, encoded_text):
        """Decode Huffman-encoded text."""
        if not self.root:
            return ""

        decoded = []
        current = self.root

        for bit in encoded_text:
            if bit == '0':
                current = current.left
            else:
                current = current.right

            # If we reach a leaf node
            if current.char is not None:
                decoded.append(current.char)
                current = self.root  # Reset to root

        return ''.join(decoded)

# Example usage
text = "hello world"
huffman_tree = HuffmanTree(text)

# Generate codes
codes = huffman_tree.generate_codes()
print("Huffman codes:")
for char, code in codes.items():
    print(f"  '{char}': {code}")

# Encode and decode
encoded = huffman_tree.encode(text)
decoded = huffman_tree.decode(encoded)

print(f"\nOriginal:  '{text}'")
print(f"Encoded:   '{encoded}'")
print(f"Decoded:   '{decoded}'")
print(f"Compression ratio: {len(encoded) / (len(text) * 8):.2f}")

Use Cases

When to Use Binary Trees

Good for:

Hierarchical data representation
Expression parsing and evaluation
Decision making systems
File system structures
Huffman coding and compression
Game trees and AI decisions
Syntax trees in compilers

Examples:

# Hierarchical organization
org_tree = BinaryTree("CEO")
org_tree.insert_left("CEO", "CTO")
org_tree.insert_right("CEO", "CFO")

# Mathematical expressions
expr_tree = BinaryTree("+")
expr_tree.insert_left("+", "3")
expr_tree.insert_right("+", "4")

# Decision processes
decision_tree = BinaryTree("condition")
decision_tree.insert_left("condition", "action_true")
decision_tree.insert_right("condition", "action_false")

When NOT to Use Binary Trees

Avoid for:

Sequential data access (use arrays/lists)
Key-value storage without ordering (use hash tables)
Queue/stack operations (use specialized structures)
Frequently changing size with balanced requirement (use self-balancing trees)

Better alternatives:

# For sequential access, use list
sequential_data = [1, 2, 3, 4, 5]
print(sequential_data[2])  # Direct access

# For key-value pairs, use dictionary
data_map = {"key1": "value1", "key2": "value2"}
print(data_map["key1"])  # O(1) lookup

# For balanced operations, use balanced tree implementations
# (AVL, Red-Black trees in other modules)

Performance Characteristics

Time Complexity Analysis

Balanced tree operations: O(log n) for search, insert, delete
Unbalanced tree operations: O(n) worst case (degrades to linked list)
Traversal operations: O(n) - must visit all nodes
Tree property calculations: O(n) - requires tree traversal

Space Complexity

Storage: O(n) for n nodes
Recursion stack: O(h) where h is height
Worst case height: O(n) for skewed tree
Best case height: O(log n) for balanced tree

Comparison with Other Tree Types

Tree Type	Search	Insert	Delete	Balanced	Use Case
Binary Tree	O(n)	O(n)	O(n)	No	General hierarchy
Binary Search Tree	O(log n)	O(log n)	O(log n)	No	Sorted data
AVL Tree	O(log n)	O(log n)	O(log n)	Yes	Frequent searches
Red-Black Tree	O(log n)	O(log n)	O(log n)	Yes	Insertions/deletions
Heap	O(n)	O(log n)	O(log n)	Complete	Priority queues

API Reference

Binary Tree Implementation

A binary tree is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child. This implementation provides a general-purpose binary tree with common operations.

Key Features:

Node insertion and deletion
Tree traversals (inorder, preorder, postorder, level-order)
Tree properties (height, size, balance checking)
Search operations
Tree validation and manipulation

Time Complexities (for a balanced tree):

Search: O(log n) average, O(n) worst case
Insert: O(log n) average, O(n) worst case
Delete: O(log n) average, O(n) worst case
Traversal: O(n)

Space Complexity: O(n) for storage, O(h) for recursion stack where h is height

`BinaryTree(root_data=None)`

Bases: BinaryTreeInterface[T]

A binary tree implementation with comprehensive operations.

This is a general binary tree (not necessarily a binary search tree), so it doesn't maintain any ordering properties.

Initialize a binary tree.

Parameters:

Name	Type	Description	Default
`root_data`	`Optional[T]`	Data for the root node (None creates empty tree)	`None`

`repr()`

Return detailed representation for debugging.

`str()`

Return string representation of the tree.

`are_identical(other)`

Check if this tree is identical to another tree.

Parameters:

Name	Type	Description	Default
`other`	`BinaryTree[T]`	Another binary tree to compare with	required

Returns:

Type	Description
`bool`	True if trees are identical, False otherwise

`delete(data)`

Delete the first node with the given data.

Parameters:

Name	Type	Description	Default
`data`	`T`	Data of the node to delete	required

Returns:

Type	Description
`bool`	True if deletion successful, False if node not found

`diameter()`

Calculate the diameter of the tree.

Diameter is the longest path between any two nodes in the tree.

Returns:

Type	Description
`int`	Diameter of the tree

`find(data)`

Check if a node with the given data exists in the tree.

Parameters:

Name	Type	Description	Default
`data`	`T`	Data to search for	required

Returns:

Type	Description
`bool`	True if found, False otherwise

`get_leaves()`

Get all leaf nodes in the tree.

Returns:

Type	Description
`List[T]`	List of data from leaf nodes

`height()`

Return the height of the tree.

Height is defined as the number of edges on the longest path from root to a leaf. Empty tree has height -1.

`inorder_traversal()`

Perform inorder traversal (left, root, right).

Returns:

Type	Description
`List[T]`	List of node data in inorder sequence

`insert_left(parent_data, new_data)`

Insert a new node as the left child of the node with parent_data.

Parameters:

Name	Type	Description	Default
`parent_data`	`T`	Data of the parent node	required
`new_data`	`T`	Data for the new node	required

Returns:

Type	Description
`bool`	True if insertion successful, False if parent not found

`insert_right(parent_data, new_data)`

Insert a new node as the right child of the node with parent_data.

Parameters:

Name	Type	Description	Default
`parent_data`	`T`	Data of the parent node	required
`new_data`	`T`	Data for the new node	required

Returns:

Type	Description
`bool`	True if insertion successful, False if parent not found

`is_balanced()`

Check if the tree is height-balanced.

A tree is balanced if the heights of the two subtrees of any node differ by at most one.

Returns:

Type	Description
`bool`	True if balanced, False otherwise

`is_empty()`

Check if the tree is empty.

`level_order_traversal()`

Perform level-order traversal (breadth-first).

Returns:

Type	Description
`List[T]`	List of node data in level-order sequence

`mirror()`

Mirror the tree (swap left and right subtrees recursively).

`postorder_traversal()`

Perform postorder traversal (left, right, root).

Returns:

Type	Description
`List[T]`	List of node data in postorder sequence

`preorder_traversal()`

Perform preorder traversal (root, left, right).

Returns:

Type	Description
`List[T]`	List of node data in preorder sequence

`size()`

Return the number of nodes in the tree.

`TreeNode(data, left=None, right=None)`

Bases: BinaryTreeNodeInterface[T]

A node in a binary tree.

Each node contains data and references to left and right children.

Initialize a tree node.

Parameters:

Name	Type	Description	Default
`data`	`T`	The data stored in this node	required
`left`	`Optional[TreeNode[T]]`	Reference to left child node	`None`
`right`	`Optional[TreeNode[T]]`	Reference to right child node	`None`

`repr()`

Return detailed string representation for debugging.

`str()`

Return string representation of the node.

`has_both_children()`

Check if this node has both left and right children.

`has_left_child()`

Check if this node has a left child.

`has_one_child()`

Check if this node has exactly one child.

`has_right_child()`

Check if this node has a right child.

`is_leaf()`

Check if this node is a leaf (has no children).

Binary Tree

Features

Time Complexities

Basic Usage

Creating and Initializing

Creating Nodes

Building Trees

Handling Existing Children

Tree Traversals

Inorder Traversal (Left-Root-Right)

Preorder Traversal (Root-Left-Right)

Postorder Traversal (Left-Right-Root)

Level-order Traversal (Breadth-First)

Traversal Comparisons

Search Operations

Finding Nodes

Working with Empty Trees

Tree Properties

Size and Height

Leaf Nodes

Balance Checking

Diameter Calculation

Tree Manipulation

Mirroring Trees

Tree Comparison

Node Deletion

Working with Different Types

String Trees

Numeric Trees

Custom Object Trees

Tree Display and Debugging

String Representation

Tree Visualization

Error Handling

Common Patterns

Building from Lists

Tree Serialization

Tree Validation

Practical Applications

Expression Trees

Decision Trees

File System Representation

Huffman Coding Tree

Use Cases

When to Use Binary Trees

When NOT to Use Binary Trees

Performance Characteristics

Time Complexity Analysis

Space Complexity

Comparison with Other Tree Types

API Reference

BinaryTree(root_data=None)

__repr__()

__str__()

are_identical(other)

delete(data)

diameter()

find(data)

get_leaves()

height()

inorder_traversal()

insert_left(parent_data, new_data)

insert_right(parent_data, new_data)

is_balanced()

is_empty()

level_order_traversal()

mirror()

postorder_traversal()

preorder_traversal()

size()

TreeNode(data, left=None, right=None)

__repr__()

__str__()

has_both_children()

has_left_child()

has_one_child()

has_right_child()

is_leaf()

`BinaryTree(root_data=None)`

`repr()`

`str()`

`are_identical(other)`

`delete(data)`

`diameter()`

`find(data)`

`get_leaves()`

`height()`

`inorder_traversal()`

`insert_left(parent_data, new_data)`

`insert_right(parent_data, new_data)`

`is_balanced()`

`is_empty()`

`level_order_traversal()`

`mirror()`

`postorder_traversal()`

`preorder_traversal()`

`size()`

`TreeNode(data, left=None, right=None)`

`repr()`

`str()`

`has_both_children()`

`has_left_child()`

`has_one_child()`

`has_right_child()`

`is_leaf()`