I use trees when the data naturally branches or when search can eliminate half the space at each decision. Hierarchies, indexes, heaps, tries, and segment trees all become easier when I draw the branches first.
The business example I like is a retail product catalog. A marketplace may have Electronics, Grocery, and Home. Under Electronics, it may have Phones and Laptops. Under Phones, it may have Premium Phones and Refurbished Phones. That hierarchy is not decoration. It drives navigation, search filters, promotions, reporting, ownership, and compliance rules.
If a discount is blocked for Premium Phones, the checkout system needs to find that category and respect the rule before it prices the cart. That is a tree doing real business work.
Tree examples with diagrams
General tree: business hierarchy
Use it when the data is naturally parent child data.
Binary tree: at most two children
Useful as a base shape for expression trees and decision trees.
Binary search tree: ordered search
Search follows left or right based on the value.
Balanced tree: keep height small
Used by ordered maps and sets to keep lookup near O(log n).
B tree: database index pages
Common in database indexes because each node can hold many keys.
Heap: priority first
Good for schedulers, incident queues, and retry systems.
Trie: prefix search
Used for autocomplete, routing prefixes, and dictionary lookup.
Segment tree: range answers
Good when a system asks range questions again and again.
Code example: catalog tree
This is a general tree, also called an n ary tree. Each category can have any number of child categories. The code can add a category, search for a category, find the path to it, and make a checkout decision.
import java.util.ArrayList;
import java.util.List;
import java.util.Optional;
final class CatalogTree {
private final Category root;
CatalogTree(String rootId, String rootName) {
this.root = new Category(rootId, rootName, false);
}
boolean addCategory(String parentId, String id, String name, boolean discountLocked) {
Optional<Category> parent = find(parentId);
if (parent.isEmpty()) {
return false;
}
parent.get().children.add(new Category(id, name, discountLocked));
return true;
}
Optional<Category> find(String id) {
return find(root, id);
}
private Optional<Category> find(Category node, String id) {
if (node.id.equals(id)) {
return Optional.of(node);
}
for (Category child : node.children) {
Optional<Category> found = find(child, id);
if (found.isPresent()) {
return found;
}
}
return Optional.empty();
}
boolean canApplyDiscount(String categoryId) {
List<Category> path = new ArrayList<>();
if (!pathTo(root, categoryId, path)) {
return false; // unknown category: fail closed
}
return path.stream().noneMatch(category -> category.discountLocked);
}
private boolean pathTo(Category node, String targetId, List<Category> path) {
path.add(node);
if (node.id.equals(targetId)) {
return true;
}
for (Category child : node.children) {
if (pathTo(child, targetId, path)) {
return true;
}
}
path.remove(path.size() - 1);
return false;
}
private static final class Category {
private final String id;
private final String name;
private final boolean discountLocked;
private final List<Category> children = new ArrayList<>();
private Category(String id, String name, boolean discountLocked) {
this.id = id;
this.name = name;
this.discountLocked = discountLocked;
}
}
}
final class CatalogTreeExample {
public static void main(String[] args) {
CatalogTree catalog = new CatalogTree("catalog", "Retail Catalog");
catalog.addCategory("catalog", "electronics", "Electronics", false);
catalog.addCategory("electronics", "phones", "Phones", false);
catalog.addCategory("phones", "premium-phones", "Premium Phones", true);
boolean allowed = catalog.canApplyDiscount("premium-phones");
System.out.println(allowed); // false
}
}The code builds a real category tree and searches it with depth first traversal. The checkout decision fails closed when the category is unknown and blocks a discount when any category on the path is marked as locked. That matters because business rules often live above the exact product being purchased.
Complexity guide
| Tree type | Best fit | Search | Insert | Delete | Important note |
|---|---|---|---|---|---|
| General tree | Catalogs, org hierarchy, approval rules | O(n) | O(n) to find parent, O(1) if parent is known | O(n) | Great for meaning, not automatically fast for search. |
| Binary tree | Expression trees, decision trees | O(n) | Depends on rule | Depends on rule | The shape alone does not guarantee fast lookup. |
| Binary search tree | Ordered values | Average O(log n), worst O(n) | Average O(log n), worst O(n) | Average O(log n), worst O(n) | Bad insertion order can turn it into a chain. |
| Balanced tree | Ordered maps and sets | O(log n) | O(log n) | O(log n) | Rotation keeps height controlled. |
| B tree | Database and storage indexes | O(log n) | O(log n) | O(log n) | Large nodes reduce disk and page reads. |
| Heap | Priority queues | O(n) | O(log n) | Remove top O(log n) | Fast at finding the top priority item. |
| Trie | Prefix lookup | O(k), where k is key length | O(k) | O(k) | Cost follows word length more than total rows. |
| Segment tree | Range queries | Range query O(log n) | Build O(n), update O(log n) | Usually updated, not deleted | Useful when the same range questions repeat often. |
When to use what
What to watch
When I talk about "What to watch", I connect the shape to the operation I want to make cheap.
A tree is only fast when its shape supports the operation. A plain hierarchy helps people understand rules, but it may still require O(n) search. A binary search tree is fast only when it stays shallow. A heap gives fast priority removal, but it is not a good structure for searching arbitrary values.
In production systems, it is common to keep the tree for meaning and add an index for speed. A catalog service may store the category tree, then build a map from category id to node after loading it. The tree explains the relationship. The index keeps hot requests fast.
Closing
My recommendation in "Closing" is to draw the data movement before memorizing the complexity table.
Trees are not interview trivia. They are one of the basic shapes behind business systems. When data branches, rules inherit, values sort, priorities compete, prefixes matter, or ranges repeat, a tree is often the simplest way to make the code match the problem.