# Module 6 - Tree
# 1. Introduction
# Module 6: Tree
#### **Author:** YP
## **Learning Objectives**
After completing this module, students are expected to be able to:
1. Explain the basic concept of a **Tree** as a non-linear data structure.
2. Identify the differences between **root, parent, child, leaf, and subtree**.
3. Implement **Traversal** methods: Inorder, Preorder, Postorder, and Level Order.
4. Understand the role of **Stack** and **Queue** in traversal algorithms.
5. Apply the concept of Trees to **real-world cases in daily life**.
# 2. Tree Concept
## **2.1 Basic Theory**
### 2.1.1 Definition of a Tree
A **Tree** is a **non-linear hierarchical** data structure composed of nodes and edges.
- Every Tree has a **root** (root node).
- The root can have **children**.
- A node with no children is called a **leaf**.
- Each node and its descendants can form a **subtree**.
### 2.1.2 Important Terms in a Tree
- **Root** → the topmost node.
- **Parent** → a node that has children.
- **Child** → a node derived from a parent.
- **Leaf** → a node without children.
- **Subtree** → a small tree formed from a node and its descendants.
### 2.1.3 Binary Tree
A **Binary Tree** is a tree data structure in which each node has at most two children (left and right).
- **There are no special rules** for placing node values.
- **Used** for hierarchical representation, data structures like heaps, expression trees, and implementing search or traversal algorithms.
- Nodes in a Binary Tree can have 0, 1, or 2 children.
**Characteristics of a Binary Tree:**
- Height of the tree: the number of levels from the root to the farthest leaf.
- Leaf node: a node that has no children.
---
## 2.2 Introduction to Stack and Queue
### **2.2.1 Stack**
A LIFO (Last In First Out) data structure → the last data in is the first one out. Example: a stack of plates in a cafeteria. The last plate placed on top will be the first one taken.
Main operations:
- push(x) → adds data to the top of the stack.
- pop() → removes data from the top of the stack.
**Application in Trees**
Used in DFS (Depth First Search) or Preorder, Inorder, Postorder traversals. When we enter a child node, the current node is stored on the stack. After finishing with the child, we pop from the stack to continue.
### **2.2.2 Queue**
A FIFO (First In First Out) data structure → the first data in is the first one out. Example: a minimarket cashier line, the person who arrives first will be served first.
Main operations:
- enqueue(x) → inserts data at the back of the queue.
- dequeue() → removes data from the front of the queue.
**Application in Trees**
Used in BFS (Breadth First Search) or Level Order traversal. When visiting a node, its children are added to the queue, then processed one by one in order.
---
## 2.3 Traversal in Trees
Traversal is the process of visiting each node in a tree.
### **2.3.1 Inorder (Left, Root, Right)**
- visit the left, then the middle (root), then the right. The result is usually data sorted in ascending order.
```cpp=
// Inorder (Left - Root - Right)
void inorder(Node* root) {
if (root == nullptr) return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
```
### **2.3.2 Preorder (Root, Left, Right)**
- visit the middle first, then the left, then the right. Used to represent the structure of the tree.
```cpp=
// Preorder (Root - Left - Right)
void preorder(Node* root) {
if (root == nullptr) return;
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
```
### **2.3.3 Postorder (Left, Right, Root)**
- visit the left first, then the right, finally the middle. Suitable if you want to delete all contents of the tree.
```cpp=
// Postorder (Left - Right - Root)
void postorder(Node* root) {
if (root == nullptr) return;
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
```
### **2.3.4 Level Order**
- Visit nodes level by level from top to bottom, left to right.
- Usually uses a queue.
```cpp
void levelOrder(Node* root) {
if (root == nullptr) return;
queue q;
q.push(root);
while (!q.empty()) {
Node* temp = q.front();
q.pop();
cout << temp->data << " ";
if (temp->left) q.push(temp->left);
if (temp->right) q.push(temp->right);
}
}
```
### **2.3.5 Traversal Illustration Example**
```
50
/ \
/ \
30 70
/ \ / \
20 40 60 80
```
- **Inorder:** 20, 30, 40, 50, 60, 70, 80
- **Preorder:** 50, 30, 20, 40, 70, 60, 80
- **Postorder:** 20, 40, 30, 60, 80, 70, 50
- **Level Order:** 50, 30, 70, 20, 40, 60, 80
---
## **References**
- GeeksforGeeks, “Binary Search Tree (BST),” [Online]. Available: https://www.geeksforgeeks.org/binary-search-tree-data-structure/. [Accessed: 20-August-2025]
- Programiz, “Tree Data Structure in C++,” [Online]. Available: https://www.programiz.com/dsa/binary-search-tree. [Accessed: 20-August-2025]