Binary Trees

December 13, 2024 | Data Structures

Binary trees are a foundational data structure in computer science, widely used in areas such as data storage, searching, and sorting. Understanding binary trees is essential for mastering advanced topics like binary search trees, heaps, and graph algorithms.

What is a Binary Tree?

A binary tree is a hierarchical data structure in which each node has at most two children:

Left child
Right child

Example of a Binary Tree

Representation of a Node in Python

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Types of Binary Trees

Full Binary Tree: Every node has either 0 or 2 children.
Complete Binary Tree: All levels except possibly the last are completely filled, and nodes in the last level are as left as possible.
Perfect Binary Tree: All internal nodes have two children, and all leaves are at the same level.
Balanced Binary Tree: The height difference between the left and right subtrees of any node is at most 1.
Binary Search Tree (BST): A binary tree where the left child’s value is less than the parent’s value, and the right child’s value is greater.

Common Operations on Binary Trees

1. Insertion

Adding a new node to the binary tree.

def insert(root, value):
    if root is None:
        return TreeNode(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

# Example usage:
root = TreeNode(10)
root = insert(root, 5)
root = insert(root, 15)
root = insert(root, 3)

2. Traversal

Visiting all nodes in a specific order. Common traversal methods include:

In-order (Left, Root, Right): Produces sorted values in a BST.
Pre-order (Root, Left, Right): Used to copy the tree structure.
Post-order (Left, Right, Root): Used to delete or free nodes.

def inorder_traversal(root):
    if root:
        inorder_traversal(root.left)
        print(root.value, end=" ")
        inorder_traversal(root.right)

# Example usage:
inorder_traversal(root)  # Output: 3 5 10 15

3. Search

Finding a node with a specific value.

def search(root, value):
    if root is None or root.value == value:
        return root is not None
    if value < root.value:
        return search(root.left, value)
    return search(root.right, value)

# Example usage:
print(search(root, 15))  # Output: True
print(search(root, 20))  # Output: False

4. Deletion

Removing a node while maintaining the tree’s structure.

def delete(root, value):
    if root is None:
        return root
    if value < root.value:
        root.left = delete(root.left, value)
    elif value > root.value:
        root.right = delete(root.right, value)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        temp = find_min(root.right)
        root.value = temp.value
        root.right = delete(root.right, temp.value)
    return root

# Helper function to find the minimum value node:
def find_min(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

Applications of Binary Trees

Searching and Sorting: Binary Search Trees are the basis of many search algorithms.
Expression Evaluation: Used in expression trees to evaluate mathematical expressions.
Data Compression: Huffman coding utilizes binary trees for efficient data encoding.
Routing and Network Optimization: Binary trees are used in various networking algorithms.