Hierarchical structures for efficient searching, sorting, and data organization.
Theory
Code
Theory & Description
A tree is a hierarchical data structure consisting of nodes connected by edges, with a single root node at the top. Each node can have zero or more child nodes, forming a parent-child relationship. Binary trees limit each node to at most two children. Binary Search Trees (BSTs) maintain a sorted order where left children are smaller and right children are larger, enabling efficient searching and sorting. Trees are the foundation for databases, file systems, and many algorithms.
Common Use Cases
- File system directory structures
- Database indexing with B-trees
- HTML/XML DOM representation
- Decision trees in machine learning
Complexity Cheat Sheet
| Operation | Average | Worst |
|---|---|---|
| Access | O(log n) | O(n) |
| Search | O(log n) | O(n) |
| Insertion | O(log n) | O(n) |
| Deletion | O(log n) | O(n) |
| Space Complexity | O(n) | |
Visualization
Problems