Trees (Binary Trees, BSTs) using Python

A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike linear data structures (like arrays, linked lists, stacks, and queues), trees represent hierarchical relationships between elements.

Key Terminologies:

Node: An entity that contains a key or value and pointers to its child nodes.
Edge: The link between two nodes.
Root: The topmost node in a tree.
Parent: A node that has child nodes.
Child: A node that has a parent node.
Leaf (or Terminal Node): A node with no children.
Internal Node: A node with at least one child.
Height of a Tree: The number of edges on the longest path from the root to a leaf.
Depth of a Node: The number of edges from the root to that node.
Degree of a Node: The number of children of that node.

Binary Tree

A binary tree is a special type of tree in which each node can have at most two children, referred to as the left child and the right child.

Properties of Binary Trees:

Each node has 0, 1, or 2 children.
Applications: Expression trees, Huffman coding trees, binary search trees.

Node representation for a Binary Tree:


class TreeNode:
    def __init__(self, key):
        self.key = key      # Data stored in the node
        self.left = None  # Pointer to the left child
        self.right = None # Pointer to the right child

Binary Search Tree (BST)

A Binary Search Tree (BST) is a binary tree with the following additional properties:

The key of the left child of a node is less than or equal to the key of its parent node.
The key of the right child of a node is greater than or equal to the key of its parent node.
Both the left and right subtrees must also be binary search trees.

BSTs allow for efficient searching, insertion, and deletion of nodes (average time complexity O(log n) for balanced trees).

BST Implementation in Python:


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

def insert(root, key):
    """Inserts a new key into the BST."""
    if root is None:
        return TreeNode(key)
    else:
        if key < root.key:
            root.left = insert(root.left, key)
        else:
            root.right = insert(root.right, key)
    return root

def inorder_traversal(root):
    """Performs an in-order traversal (Left, Root, Right) of the BST."""
    result = []
    if root:
        result.extend(inorder_traversal(root.left))
        result.append(root.key)
        result.extend(inorder_traversal(root.right))
    return result

def search(root, key):
    """Searches for a key in the BST."""
    if root is None or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    return search(root.right, key)

# Example Usage:
root_bst = None
keys_to_insert = [50, 30, 20, 40, 70, 60, 80]

for key_val in keys_to_insert:
    root_bst = insert(root_bst, key_val)

print(f"In-order traversal of BST: {inorder_traversal(root_bst)}")
# Output: In-order traversal of BST: [20, 30, 40, 50, 60, 70, 80]

search_key = 40
found_node = search(root_bst, search_key)
if found_node:
    print(f"Key {search_key} found in BST.")
else:
    print(f"Key {search_key} not found in BST.")

search_key_missing = 90
found_node_missing = search(root_bst, search_key_missing)
if found_node_missing:
    print(f"Key {search_key_missing} found in BST.")
else:
    print(f"Key {search_key_missing} not found in BST.")

Tree Traversals:

Traversing a tree means visiting all its nodes in a specific order. Common traversal methods for binary trees are:

In-order (Left, Root, Right): Visits the left subtree, then the root, then the right subtree. For a BST, this yields nodes in non-decreasing order.
Pre-order (Root, Left, Right): Visits the root, then the left subtree, then the right subtree. Useful for creating a copy of the tree.
Post-order (Left, Right, Root): Visits the left subtree, then the right subtree, then the root. Useful for deleting nodes or evaluating expression trees.
Level-order (Breadth-First): Visits nodes level by level, from left to right. Typically implemented using a queue.

Advantages of Trees:

Represent hierarchical relationships naturally.
Efficient searching and sorting (especially BSTs).
Dynamic size.

Disadvantages of Trees:

Can be complex to implement and manage, especially balancing operations (e.g., AVL trees, Red-Black trees).
Unbalanced trees can degrade performance to O(n) for search/insert/delete operations (similar to a linked list).
Pointers can consume significant memory.

Applications of Trees:

File systems (directory structures).
Organization charts.
Decision trees in machine learning.
Syntax trees in compilers.
Network routing algorithms.
Database indexing (e.g., B-trees, B+ trees).