Ugenz Academy/Tutorial

Trees

15 min read2,818 words

Reading progress

Keep learning

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:

  • n nodes
  • n - 1 edges
  • 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:

DFSBFS
Goes deep firstGoes level by level
Uses stack/recursionUses queue
Good for paths/subtreesGood for level-based problems
Often recursiveUsually iterative
Memory depends on depth/structureCan 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

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy