Trees - Data Structures

A tree is a hierarchical data structure consisting of nodes connected by edges. Each tree has a root node and zero or more subtrees.

Introduction

Trees are non-linear data structures that represent hierarchical relationships. They are widely used in computer science for organizing data efficiently.

Tree Terminology

• Root: The topmost node
• Parent: A node that has children
• Child: A node connected to a parent
• Leaf: A node with no children
• Height: Number of edges from root to deepest leaf
• Depth: Number of edges from root to a node

Types of Trees

1. Binary Tree

Each node has at most two children (left and right).

2. Binary Search Tree (BST)

A binary tree where:

• Left subtree contains values less than root
• Right subtree contains values greater than root

3. AVL Tree

A self-balancing binary search tree where the difference between heights of left and right subtrees is at most 1.

4. B-Tree

A self-balancing tree data structure that maintains sorted data and allows searches, sequential access, and insertions/deletions in logarithmic time.

Tree Traversals

1. Inorder (Left, Root, Right)

def inorder(root):
    if root:
        inorder(root.left)
        print(root.data)
        inorder(root.right)

2. Preorder (Root, Left, Right)

def preorder(root):
    if root:
        print(root.data)
        preorder(root.left)
        preorder(root.right)

3. Postorder (Left, Right, Root)

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.data)

4. Level Order (Breadth-First)

Uses a queue to visit nodes level by level.

Common Tree Problems

1. Maximum depth of binary tree
2. Same tree check
3. Symmetric tree
4. Binary tree level order traversal
5. Construct tree from preorder and inorder
6. Validate BST
7. Lowest common ancestor
8. Path sum problems

Applications

• File system representation
• Database indexing
• Expression parsing
• Decision trees
• Priority queues (heap)
• Network routing algorithms