Trees
A Tree is a non-linear data structure used to represent data in a hierarchical relationship.
Examples from real life:
- Computer file systems
- Organization structures
- Family trees
- HTML DOM
- Database indexes
- Decision trees
- Routing structures
The most important idea is:
A tree is made of nodes connected by edges, with one node at the top called the root.
1. Why Do We Need Trees?
So far, we have studied mostly linear structures:
Array: [10] → [20] → [30] → [40] Linked List: 10 → 20 → 30 → 40 Stack: 40 30 20 10 Queue: 10 → 20 → 30 → 40
These structures are mainly linear.
But many real-world relationships are hierarchical.
For example, a computer folder:
Documents │ ├── College │ ├── DSA │ ├── C++ │ └── Networks │ ├── Projects │ ├── IoT │ └── Web │ └── Resume
This is naturally represented using a tree.
2. Basic Tree Structure
Consider:
A / \ B C / \ \ D E F
Here:
A = Root B, C = Children of A D, E = Children of B F = Child of C
The connections are called edges.
3. Important Tree Terminology
You need to know these terms very well.
Root
The topmost node.
A / \ B C
A is the root.
A tree has exactly one root.
Node
Every element in the tree is called a node.
A / \ B C
There are 3 nodes:
A B C
Edge
The connection between two nodes.
A ─── B
The line between A and B is an edge.
If a tree has n nodes, it always has:
n - 1 edges
For example:
5 nodes ↓ 4 edges
4. Parent and Child
Consider:
A / \ B C / \ D E
A is the parent of B and C.
A ├── B └── C
B is the parent of D and E.
B ├── D └── E
Therefore:
A → Parent B,C → Children
5. Siblings
Nodes having the same parent are called siblings.
A / | \ B C D
B, C, and D are siblings.
6. Leaf Node
A node that has no children is called a leaf node.
Example:
A / \ B C / \ D E
Leaf nodes:
C D E
Because they have no children.
7. Internal Node
A node that has at least one child is generally called an internal node or non-leaf node.
In:
A / \ B C / \ D E
Internal nodes:
A B
8. Degree of a Node
The degree of a node is the number of children it has.
Example:
A / | \ B C D
Degree of A:
3
Degree of B, C, and D:
0
9. Degree of a Tree
The degree of a tree is the maximum degree of any node.
Example:
A / | \ B C D / \ E F
Degrees:
A → 3 B → 0 C → 2 D → 0
Therefore:
Degree of tree = 3
10. Depth
The depth of a node is the number of edges from the root to that node.
Consider:
A / \ B C / \ D E / F
Depth:
A → 0 B → 1 C → 1 D → 2 E → 2 F → 3
So:
Depth = distance from root
11. Height
The height of a node is the number of edges on the longest path from that node down to a leaf.
For:
A / \ B C / D / E
Height of A:
A → B → D → E
There are 3 edges.
So:
height(A) = 3
The height of a tree is the height of its root.
12. Depth vs Height
This is commonly confusing.
Depth
Think:
How far DOWN is this node from the root?
Root ↓ ↓ Node
Height
Think:
How far DOWN can we go from this node?
Node ↓ ↓ Leaf
So:
Depth → Root to Node Height → Node to deepest Leaf
13. Level
Level is commonly defined as depth + 1.
For example:
Level 1 → A Level 2 → B C Level 3 → D E F
Some books use root level 0, so always check the convention being used.
For DSA problems, depth starting at 0 is extremely common.
14. Ancestor
An ancestor is a node that appears above another node on its path to the root.
Example:
A / B / C / D
Ancestors of D:
C B A
15. Descendant
The opposite of ancestor.
In:
A / B / \ C D
Descendants of A:
B C D
16. Subtree
A node together with all its descendants forms a subtree.
Consider:
A / \ B C / \ D E
The subtree rooted at B is:
B / \ D E
Every node can be considered the root of its own subtree.
This concept becomes extremely important in:
- Tree recursion
- Binary trees
- BST
- Dynamic programming on trees
17. Path
A path is a sequence of connected nodes.
For:
A / B / D / F
Path from A to F:
A → B → D → F
There are 3 edges.
18. Important Property of Trees
A tree is:
Connected and contains no cycles.
For example:
A | B | C
is a tree.
But:
A ─── B \ / C
contains a cycle.
That's not a tree.
19. Tree vs Graph
A tree is actually a special type of graph.
A tree has:
nnodesn - 1edges- Connected
- No cycles
A general graph may have:
- Any number of edges
- Cycles
- Multiple paths
- Possibly disconnected components
So:
Graph ↓ Special case ↓ Tree
Later, your Graphs topic will build on this.
20. Types of Trees
There are many types of trees.
Important ones in DSA:
Tree │ ├── General Tree │ ├── Binary Tree │ ├── Binary Search Tree │ ├── Heap │ ├── Trie │ ├── AVL Tree │ └── B-Tree
Your roadmap separately covers:
Trees ↓ Binary Tree ↓ BST ↓ Heap ↓ Priority Queue ↓ Trie
So here we'll focus mainly on general tree concepts.
21. General Tree
A general tree allows a node to have any number of children.
Example:
A / | \ B C D / \ / \ E F G H
A has 3 children.
B has 2.
C has 0.
There is no fixed maximum number of children.
22. Binary Tree
A binary tree is a tree where each node has at most two children.
The children are called:
Left Child Right Child
Example:
A / \ B C / \ D E
Notice:
B → left = D B → right = E
Binary trees are extremely important and have their own topic next.
23. Tree Representation in C++
A general tree can be represented in different ways.
One simple representation is:
struct Node { int data; vector<Node*> children; };
Example:
Node* root = new Node(); root->data = 1;
Then we can add children:
Node* child1 = new Node(); child1->data = 2; Node* child2 = new Node(); child2->data = 3; root->children.push_back(child1); root->children.push_back(child2);
Conceptually:
1 / \ 2 3
24. Better C++ Structure
A more complete version:
#include <iostream> #include <vector> using namespace std; struct Node { int data; vector<Node*> children; Node(int value) { data = value; } };
We can create:
Node* root = new Node(10); root->children.push_back(new Node(20)); root->children.push_back(new Node(30)); root->children.push_back(new Node(40));
Tree:
10 / | \ 20 30 40
25. Traversing a Tree
Traversal means:
Visiting every node in the tree.
This is one of the most important tree concepts.
For a general tree, we commonly use:
- DFS
- BFS
26. DFS — Depth First Search
DFS explores as deeply as possible before moving to another branch.
Example:
A / \ B C / \ D E
DFS might visit:
A → B → D → E → C
Think:
Go deep ↓ Go deeper ↓ Reach end ↓ Come back ↓ Try next branch
DFS is strongly connected to:
Recursion + Stack
27. Recursive DFS
For a general tree:
void dfs(Node* root) { if (root == nullptr) { return; } cout << root->data << " "; for (Node* child : root->children) { dfs(child); } }
This is an excellent example of the recursion you just learned.
28. BFS — Breadth First Search
BFS visits nodes level by level.
Example:
A / \ B C / \ \ D E F
BFS:
A B C D E F
Traversal:
A → B → C → D → E → F
BFS uses a:
Queue
Remember your Queue topic?
This is where it becomes useful.
29. BFS Using Queue
#include <queue> void bfs(Node* root) { if (root == nullptr) { return; } queue<Node*> q; q.push(root); while (!q.empty()) { Node* current = q.front(); q.pop(); cout << current->data << " "; for (Node* child : current->children) { q.push(child); } } }
The process:
Root ↓ Queue ↓ Remove front ↓ Visit node ↓ Add children ↓ Repeat
30. DFS vs BFS
Very important:
| DFS | BFS |
|---|---|
| Goes deep first | Goes level by level |
| Uses stack/recursion | Uses queue |
| Good for paths/subtrees | Good for level-based problems |
| Often recursive | Usually iterative |
| Memory depends on depth/structure | Can hold an entire level |
Think:
DFS → Deep BFS → Wide
31. Tree Traversal Example
Consider:
1 / | \ 2 3 4 / \ 5 6
DFS
One possible preorder-style traversal:
1 2 5 6 3 4
BFS
1 2 3 4 5 6
32. Tree Height Using Recursion
Suppose:
1 / \ 2 3 / 4
We can recursively calculate height.
int height(Node* root) { if (root == nullptr) { return -1; } int maxHeight = -1; for (Node* child : root->children) { maxHeight = max(maxHeight, height(child)); } return maxHeight + 1; }
Why recursion?
Because:
The height of a tree depends on the height of its subtrees.
That's a perfect recursive problem.
33. Counting Nodes
We can count all nodes recursively.
int countNodes(Node* root) { if (root == nullptr) { return 0; } int count = 1; for (Node* child : root->children) { count += countNodes(child); } return count; }
The logic:
Current node + nodes in child 1 + nodes in child 2 + nodes in child 3 ...
34. Counting Leaf Nodes
A leaf has no children.
int countLeaves(Node* root) { if (root == nullptr) { return 0; } if (root->children.empty()) { return 1; } int count = 0; for (Node* child : root->children) { count += countLeaves(child); } return count; }
This is another example of:
Tree ↓ Subtrees ↓ Recursion
35. Why Trees and Recursion Are Closely Connected
This is one of the most important ideas in DSA.
A tree naturally breaks into smaller trees.
Consider:
A / \ B C / \ D E
The tree rooted at A contains:
Subtree B Subtree C
So we can think:
Solve tree ↓ Solve left/smaller subtree ↓ Solve right/smaller subtree ↓ Combine results
This is why tree algorithms are frequently recursive.
36. Balanced vs Skewed Tree
A tree can have different shapes.
Balanced-ish
A / \ B C / \ / \ D E F G
The height is relatively small.
Skewed
A \ B \ C \ D \ E
This looks almost like a linked list.
This difference becomes extremely important for:
- Binary Search Trees
- Searching
- Insertion
- Deletion
- Complexity
37. Tree Complexity
For a general tree with n nodes:
Traversal
DFS visits every node:
O(n)
BFS also visits every node:
O(n)
Search
Without any special ordering:
O(n)
because we may need to inspect every node.
Space
DFS recursion:
O(h)
where h is tree height, ignoring the storage of the tree itself.
BFS can require:
O(w)
where w is the maximum width of the tree.
38. Tree vs Linked List
A linked list:
10 → 20 → 30 → 40
is essentially a very restricted tree-like structure.
A tree:
10 / \ 20 30 / \ 40 50
allows branching.
So:
Linked List → One direction/branch Tree → Multiple branches
39. Important Tree Properties
For a tree containing n nodes:
Number of edges
n - 1
Exactly one path
There is exactly one simple path between any two nodes in a tree.
For:
A / \ B C / D
Path from D to C:
D → B → A → C
There isn't another path.
40. Common Tree Applications
Trees are used extensively in computer science.
File systems
Computer ├── Users ├── Program Files └── Documents
HTML DOM
html ├── head └── body ├── div └── p
Organization
CEO ├── Manager │ ├── Employee │ └── Employee └── Manager
Databases
Trees are used in database indexes.
Compilers
Syntax trees represent program structure.
AI
Decision trees represent decisions.
Networking
Some routing structures can be represented as trees.
41. Tree Data Structure Roadmap
Your upcoming topics are actually different specialized tree structures.
TREE │ ┌───────────┴───────────┐ ↓ ↓ General Tree Binary Tree │ ↓ Binary Search Tree │ ┌──────────┴──────────┐ ↓ ↓ Heap Other BSTs ↓ Priority Queue
And separately:
Tree ↓ Trie
These structures solve different problems.
42. General Tree vs Binary Tree
This distinction is important.
General Tree
A node can have any number of children.
A / / \ \ B C D E
Binary Tree
A node can have at most 2 children.
A / \ B C / \ D E
The two positions are specifically:
Left Child Right Child
43. Important Tree Questions
Before moving to Binary Trees, make sure you can answer:
Basic
- What is a tree?
- What is a root?
- What is a node?
- What is an edge?
- What is a parent?
- What is a child?
- What are siblings?
- What is a leaf?
- What is an internal node?
Structural
- What is degree?
- What is depth?
- What is height?
- What is a subtree?
- What is an ancestor?
- What is a descendant?
- What is a path?
Algorithms
- What is DFS?
- What is BFS?
- Which data structure does DFS use?
- Which data structure does BFS use?
- Why is recursion useful for trees?
🧠 Final Mental Model
Think of a tree like this:
ROOT │ ┌────────────┴────────────┐ │ │ CHILD CHILD │ │ ┌─────┴─────┐ │ │ │ │ CHILD CHILD CHILD │ LEAF
And remember:
Node ↓ Children ↓ Subtrees ↓ Recursion ↓ DFS / BFS
Most important formulas/concepts
Tree with n nodes ↓ Edges = n - 1 Depth ↓ Distance from root Height ↓ Longest downward path to leaf DFS ↓ Depth first ↓ Stack / Recursion BFS ↓ Level first ↓ Queue