Why should you care?
Not all data is naturally organized in a straight line.
Consider:
- A file system with folders inside folders
- An organization's management hierarchy
- HTML elements nested inside other elements
- Database indexes
- Decision-making systems
- Autocomplete structures
- Search algorithms
These relationships are hierarchical, not linear.
A tree is a data structure designed specifically for representing hierarchical relationships.
Trees are also the foundation for several important computer science structures, including Binary Search Trees, Heaps, Tries, and syntax trees.
The Problem
Arrays, linked lists, stacks, and queues are primarily linear data structures:
A → B → C → D
But imagine a file system:
Computer
├── Documents
│ ├── Resume.pdf
│ └── Notes.txt
├── Pictures
│ ├── Photo1.jpg
│ └── Photo2.jpg
└── Videos
└── Movie.mp4
A simple sequence doesn't naturally represent this structure.
We need a data structure where:
One element can have multiple related elements beneath it, creating a hierarchy.
That's what a tree provides.
The Concept
A tree is a non-linear data structure made up of nodes connected by edges, where nodes form a hierarchical relationship.
A simple tree looks like this:
A
/ \
B C
/ \ \
D E F
Here:
-
Ais the root -
BandCare children ofA -
DandEare children ofB -
Fis a child ofC
Unlike a linked list:
A → B → C → D
a tree can branch:
A
/ \
B C
/ \
D E
This branching structure is what makes trees powerful.
Simple Explanation
Think of a tree like a family tree.
For example:
Grandparent
/ \
Parent A Parent B
/ \ \
Child Child Child
One person can have multiple children.
Each child can have their own children.
The structure naturally creates levels:
Level 0: A
Level 1: B C
Level 2: D E F G
A computer tree works in essentially the same way.
Each node can contain:
Data
+
References to children
For example:
[A]
/ \
[B] [C]
The node A stores references to B and C.
Real-world Analogy
Imagine a company's organizational structure.
At the top is the CEO:
CEO
/ \
CTO CFO
/ \ |
Dev1 Dev2 Finance
The CEO manages executives.
Executives manage teams.
Teams contain employees.
This is hierarchical information, so a tree is a natural representation.
The same structure can represent:
Company
↓
Department
↓
Team
↓
Employee
Code Example
A simple binary tree node in Java can be defined as:
class Node {
int data;
Node left;
Node right;
Node(int data) {
this.data = data;
}
}
Here each node has:
data
left child
right child
We can construct a tree:
Node root = new Node(10);
root.left = new Node(20);
root.right = new Node(30);
root.left.left = new Node(40);
root.left.right = new Node(50);
This produces:
10
/ \
20 30
/ \
40 50
The variable:
root
points to the first node of the tree.
Unlike a linked list, a node can point to multiple nodes.
Traversing a tree
One common way to visit every node is depth-first traversal.
For example, an inorder traversal:
void inorder(Node root) {
if (root == null)
return;
inorder(root.left);
System.out.println(root.data);
inorder(root.right);
}
For:
10
/ \
20 30
/ \
40 50
the inorder traversal produces:
40
20
50
10
30
The important idea is that tree algorithms are often recursive because each subtree is itself a smaller tree.
Common Mistakes
Mistake 1: Thinking every tree is a binary tree
A tree can have any number of children.
For example:
A
/ | \
B C D
/|\
E F G
This is a tree, but not a binary tree.
A binary tree specifically allows each node to have at most two children:
A
/ \
B C
So:
Tree ≠ Binary Tree
A binary tree is a specific type of tree.
Mistake 2: Confusing tree depth and height
These terms are related but are not always defined identically across texts.
A common convention is:
- Depth of a node = number of edges from the root to that node.
- Height of a node = number of edges on the longest downward path to a leaf.
- Height of the tree = height of its root.
For:
A
/
B
/
C
the depths are:
A → 0
B → 1
C → 2
The tree's height is:
2
Always check the convention being used, especially in exams or documentation.
Mistake 3: Assuming trees are automatically fast
A tree isn't automatically efficient.
Consider:
10
\
20
\
30
\
40
\
50
This tree has effectively become a linked list.
Searching it can require:
10 → 20 → 30 → 40 → 50
which is O(n).
Balanced trees are important because they keep the height relatively small.
Advanced Notes
1. Important tree terminology
Consider:
A
/ \
B C
/ \
D E
| Term | Meaning |
|---|---|
| Root | Top node (A) |
| Parent | Node directly above another node |
| Child | Node directly below another node |
| Sibling | Nodes sharing the same parent |
| Leaf | Node with no children |
| Edge | Connection between two nodes |
| Subtree | A node and its descendants |
| Depth | Distance from root to a node |
| Height | Longest downward path |
So:
A → Root
B → Parent of D and E
D → Leaf
B and C → Siblings
2. Binary trees
A binary tree allows each node to have at most two children:
10
/ \
20 30
/ \
40 50
The two possible child references are commonly called:
left
right
This structure is extremely important because it forms the basis for several other data structures.
3. Binary Search Trees
A Binary Search Tree (BST) adds an ordering rule.
For a common BST convention:
Values smaller than node → left
Values larger than node → right
For example:
50
/ \
30 70
/ \ / \
20 40 60 80
To search for 60:
60 < 50? No → go right
60 < 70? Yes → go left
Found 60
A well-balanced BST can provide approximately:
Search → O(log n)
Insert → O(log n)
Delete → O(log n)
But an unbalanced BST can degrade toward:
O(n)
4. Tree traversal
Unlike an array, there isn't just one obvious way to visit every tree node.
Three important depth-first traversals are:
Preorder
Root → Left → Right
Inorder
Left → Root → Right
Postorder
Left → Right → Root
For:
A
/ \
B C
we get:
Preorder: A B C
Inorder: B A C
Postorder: B C A
There is also level-order traversal, which processes nodes level by level:
A → B → C → D → E
Level-order traversal is commonly implemented using a queue.
5. Trees and recursion
Trees naturally fit recursive thinking.
Consider:
A
/ \
B C
The tree can be described as:
Tree A
├── Tree B
└── Tree C
Each child is itself the root of another subtree.
That's why recursive algorithms are so common with trees:
void traverse(Node node) {
if (node == null)
return;
traverse(node.left);
traverse(node.right);
}
This connects directly to the call stack you learned about earlier.
Every recursive call creates a new stack frame.
6. Heap
A heap is another important tree-based structure.
A min-heap follows a rule such as:
Parent ≤ Children
Example:
10
/ \
20 30
/ \
40 50
The smallest element is always at the root.
Heaps are commonly used to implement priority queues.
So the concepts connect:
Tree
↓
Heap
↓
Priority Queue
7. Tries
A Trie is a tree specialized for storing strings.
For example, storing:
cat
car
can
can produce a structure that shares common prefixes:
c
|
a
/ | \
t r n
Tries are useful for:
- Autocomplete
- Prefix searching
- Dictionaries
- Spell checking
The Bigger Picture
Trees represent the transition from linear structures to hierarchical structures.
The progression looks like:
Arrays
↓
Linked Lists
↓
Stacks / Queues
↓
Trees
↓
Graphs
And trees themselves form a family:
Tree
├── Binary Tree
│ ├── Binary Search Tree
│ └── Heap
│
├── Trie
│
└── Other specialized trees
Trees are also deeply connected to algorithms.
For example:
Tree
├── Searching
├── Sorting
├── Recursion
├── Parsing
├── Scheduling
└── Database indexing
Even a programming language can represent code as a tree.
For example:
a + b * c
can be represented as an Abstract Syntax Tree (AST):
+
/ \
a *
/ \
b c
The structure captures the fact that multiplication happens before addition.
So trees aren't merely a data structure—they are a way of representing hierarchical relationships and structure.
The Most Important Mental Model
A tree is a collection of nodes where relationships branch downward from a root.
Think:
ROOT
↓
┌─────┐
│ A │
└─────┘
/ \
↓ ↓
┌───┐ ┌───┐
│ B │ │ C │
└───┘ └───┘
/ \
↓ ↓
┌───┐ ┌───┐
│ D │ │ E │
└───┘ └───┘
The most important distinction is:
Linked List:
A → B → C → D
Tree:
A
/ \
B C
/ \
D E
A linked list gives you a chain.
A tree gives you branches.
Summary
A tree is a non-linear data structure used to represent hierarchical relationships.
The key ideas are:
- A tree consists of nodes and edges.
- The top node is the root.
- Nodes can have children.
- Nodes without children are leaves.
- A binary tree allows at most two children per node.
- A Binary Search Tree organizes values to support efficient searching.
- Tree traversal can be preorder, inorder, postorder, or level-order.
- Balanced trees can provide efficient operations such as O(log n) search.
- Heaps and tries are specialized tree structures.
- Trees naturally work with recursion.
- Trees are widely used in file systems, databases, compilers, search algorithms, and many other systems.
If linked lists teach you to think in chains, trees teach you to think in hierarchies—and that shift is what allows computers to efficiently represent everything from file systems to search indexes and program structure.
Top comments (0)