1. Tree Basics
A tree is a hierarchical data structure consisting of nodes, where each node has a parent (except the root) and zero or more children. Trees are a type of graph with no cycles and a single connected component.
Types of Trees:
- Binary Tree: Each node has at most two children (left and right).
- Binary Search Tree (BST): A binary tree where left child < parent < right child.
- AVL Tree: A self-balancing BST where the height difference between left and right subtrees is at most 1.
- Red-Black Tree: A self-balancing BST with additional properties for maintaining balance.
- Trie (Prefix Tree): Used for storing dynamic sets of strings.
- Segment Tree: Used for range query problems.
Tree Terminology:
- Root: The topmost node.
- Leaf: A node with no children.
- Height: Longest path from root to a leaf.
- Depth: Distance from the root to a node.
2. Tree Traversal Algorithms
2.1 Inorder Traversal (Left, Root, Right)
Description: Visits nodes in ascending order for a BST.
Example Tree:
4
/ \
2 5
/ \
1 3
Traversal Order: 1 → 2 → 3 → 4 → 5
Steps (Recursive):
- Traverse the left subtree.
- Visit the root node.
- Traverse the right subtree.
Time Complexity: O(n)
Space Complexity: O(h) (h = height of tree)
2.2 Preorder Traversal (Root, Left, Right)
Description: Useful for creating a copy of the tree.
Traversal Order: 4 → 2 → 1 → 3 → 5
Steps (Recursive):
- Visit the root node.
- Traverse the left subtree.
- Traverse the right subtree.
Time Complexity: O(n)
Space Complexity: O(h)
2.3 Postorder Traversal (Left, Right, Root)
Description: Useful for deleting a tree.
Traversal Order: 1 → 3 → 2 → 5 → 4
Steps (Recursive):
- Traverse the left subtree.
- Traverse the right subtree.
- Visit the root node.
Time Complexity: O(n)
Space Complexity: O(h)
2.4 Level Order Traversal (Breadth-First Search)
Description: Visits nodes level by level using a queue.
Traversal Order: 4 → 2 → 5 → 1 → 3
Steps (Using a Queue):
- Enqueue the root node.
- While the queue is not empty:
- Dequeue a node and process it.
- Enqueue its children.
Time Complexity: O(n)
Space Complexity: O(n) (for the queue)
3. Binary Search Tree (BST) Operations
3.1 Insertion in BST
Steps:
- Start at the root.
- Compare the value:
- If less, go to the left subtree.
- If greater, go to the right subtree.
- Insert the new node at the appropriate position.
Time Complexity:
- Average: O(log n)
- Worst (skewed tree): O(n)
3.2 Deletion in BST
Steps:
- Find the node to delete.
- Handle cases:
- Node has no children: Remove it.
- Node has one child: Replace it with its child.
- Node has two children: Replace it with its inorder successor or predecessor.
Time Complexity:
- Average: O(log n)
- Worst: O(n)
4. AVL Tree
Description: A self-balancing BST where the height difference between left and right subtrees is at most 1.
Rotations for Balancing:
- Left Rotation (LL Case)
- Right Rotation (RR Case)
- Left-Right Rotation (LR Case)
- Right-Left Rotation (RL Case)
Time Complexity:
- Search: O(log n)
- Insertion: O(log n)
- Deletion: O(log n)
5. Red-Black Tree
Description: A self-balancing BST that maintains balance through node coloring (Red or Black) and specific rules.
Properties:
- Every node is either red or black.
- The root and leaves (null nodes) are black.
- Red nodes cannot have red children (no two consecutive reds).
- Every path from a node to descendant null nodes must contain the same number of black nodes.
Time Complexity:
- Search: O(log n)
- Insertion: O(log n)
- Deletion: O(log n)
6. Trie (Prefix Tree)
Description: A tree used for storing and searching strings, where edges represent characters.
Operations:
- Insertion: Add characters level by level.
- Search: Follow characters down the tree.
Time Complexity:
- Insertion: O(m) (m = length of the string)
- Search: O(m)
Applications:
- Auto-completion
- Spell checking
7. Segment Tree
Description: A tree for answering range queries (e.g., sum, minimum, maximum).
Construction:
- Build recursively by dividing the array.
Operations:
- Query: O(log n)
- Update: O(log n)
8. Comparison of Tree Algorithms
| Algorithm | Search (Time) | Insert (Time) | Delete (Time) | Space | Balanced? |
|---|---|---|---|---|---|
| Binary Search Tree | O(log n) / O(n) | O(log n) / O(n) | O(log n) / O(n) | O(n) | No (Unbalanced) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(n) | Yes |
| Red-Black Tree | O(log n) | O(log n) | O(log n) | O(n) | Yes |
| Trie | O(m) | O(m) | O(m) | O(m * n) | N/A (for strings) |
| Segment Tree | O(log n) | O(log n) | O(log n) | O(n) | Yes |
Which Tree Algorithm to Use?
- BST: For simple searching and insertion if balance is not an issue.
- AVL Tree: When frequent search operations are required, and the tree must remain balanced.
- Red-Black Tree: When insertion and deletion are frequent, and balance must be maintained.
- Trie: For string-based applications like autocomplete and prefix searching.
- Segment Tree: For range queries and updates over an array.