Module 3: Trees

Lesson 3.1: Introduction to Trees

Trees are hierarchical data structures that reflect a parent-child relationship. They are non-linear and allow for efficient searching, insertion, and deletion. Each node contains data and references to its child nodes. Trees begin with a root node and expand downward. Trees are essential in representing structured data and are widely used in computer science for their efficiency and versatility.

Trees are dynamic, non-linear structures composed of nodes connected by edges. The topmost node is the root, and each node may have children, forming branches. Unlike arrays and lists, trees model hierarchical relationships, making them ideal for organizing structured data. They support recursive operations for searching and manipulation and are highly efficient in terms of memory and performance. You'll encounter trees in file systems, routing tables, compiler design, and AI decision models. Types of trees include Binary Trees, Binary Search Trees, AVL Trees, and more. Mastering trees enhances understanding of complex systems and improves algorithmic thinking in interviews and real-world applications.

🌳 Key Concepts & Real-World Uses

Used in operating systems for directory structures.
Enables auto-suggestions in search engines using prefix trees.
Binary Trees are used in expression evaluation and parsing.
Trees help with decision-making algorithms like game AI.
In XML/HTML, the document structure is represented as a tree.
Databases use B-Trees/B+ Trees for indexing.
Routing algorithms in networks use spanning trees.

🧪 Examples

// Example 1: Binary Tree Node in C++
struct Node {
  int data;
  Node* left;
  Node* right;
};

# Example 2: Basic Tree Structure in Python
class Node:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None

📌 Tree structures are foundational to many system-level and user-facing technologies like databases, compilers, and UI elements.

Lesson 3.2: Binary Trees & Traversals

Binary trees are a type of tree where each node has at most two children. Traversals allow you to visit all nodes in a systematic way. Inorder (LNR), Preorder (NLR), Postorder (LRN), and Level-order are key strategies. They are vital in algorithms, expression parsing, and tree manipulation. Understanding these is foundational to solving hierarchical problems efficiently.

🌳 Key Concepts & Real-World Uses

Expression trees use postorder traversal to evaluate equations.
Preorder traversal helps with copying tree structures.
Inorder traversal yields sorted data in BSTs.
Level-order traversal is used in serialization of trees.
Preorder helps create prefix notation in compilers.
Decision trees in AI are based on preorder traversal.
Used in hierarchical menu navigation in UIs.

🧪 Examples

// Example 1: Inorder Traversal in C++
void inorder(Node* root) {
  if (root == nullptr) return;
  inorder(root->left);
  cout << root->data << " ";
  inorder(root->right);
}

# Example 2: Preorder Traversal in Python
def preorder(node):
  if node:
    print(node.data)
    preorder(node.left)
    preorder(node.right)

Lesson 3.3: Binary Search Trees (BST)

Binary Search Trees (BST) are a special kind of binary tree that stores data in a sorted structure. For every node, values in the left subtree are less than the node’s value, and those in the right are greater. This allows for efficient search, insertion, and deletion — typically in O(log n) time for balanced BSTs. They are widely used in databases, memory allocators, and real-time applications that require fast lookups.

🌳 Key Concepts & Real-World Uses

Used in database indexing for fast record retrieval.
In-memory search engines often use BST-like structures.
Used in compilers for constant expression folding.
Helps implement associative arrays and sets.
Can be converted to sorted arrays using inorder traversal.
Forms the base for balanced variants like AVL and Red-Black Trees.
Real-time leaderboards use BST to maintain ranking.

🧪 Examples

// Example 1: BST Insert in C++
Node* insert(Node* root, int key) {
  if (!root) return new Node(key);
  if (key < root->data)
    root->left = insert(root->left, key);
  else
    root->right = insert(root->right, key);
  return root;
}

# Example 2: BST Search in Python
def search(node, val):
  if node is None or node.data == val:
    return node
  if val < node.data:
    return search(node.left, val)
  return search(node.right, val)