Data Structure - 11 Tree Traversal

The Tree Traversal slide the Data Structures course include:
1. Concept of tree traversal
2. Key terms of tree traversal
3. Category of tree traversal
4. Depth-first traversal
5. Breadth-first traversal
6. Importance of tree traversal
7. Application of tree traversal

1. Department of Informatics
Faculty of Industrial Engineering
Universitas Pembangunan Nasional “Veteran” Yogyakarta
Data
Structure
Andi Nurkholis, S.Kom., M.Kom.
Tree
Traversal
November 17, 2025

2. Concept of Tree Traversal
Tree traversal is the systematic process
of visiting each node in a tree structure
to read, process, or manipulate the data
stored within it.
This process plays a crucial role in
searching, sorting, expression
evaluation, and hierarchical structure
processing, which can be performed
either recursively or iteratively
depending on the type of tree and the
processing objective.

3. Key Terms of Tree Traversal
Basic terms related to trees:
üNode: The fundamental element in a tree that stores data.
üRoot: The topmost node in a tree.
üLeaf Node: A node that has no children.
üSubtree: A tree structure contained within another tree.
üHeight & Depth: Height is the length of the longest path from a node to a
leaf, while depth is the length of the path from the root to that node.

4. Key Terms of Tree Traversal
There are several common traversal methods, each with different purposes and
approaches. As an illustration, consider the following tree:
A
/ \
B C
/ \ \
D E F
üPreorder: A B D E C F
üInorder: D B E A C F
üPostorder: D E B F C A
üLevel-order: A B C D E F

5. Category ofTree Traversal
1.Depth-First Traversal (DFT)
2.Breadth-First Traversal (BFT)

6. Depth-First Traversal
Traversal that focuses on exploring each
branch of the tree as deeply as possible before
moving to another branch. DFT is typically
implemented recursively, though it can also be
done using a stack. The types of DFT include:
üPreorder Traversal (Root – Left – Right):
The root node is visited first, followed by the
left subtree, and finally the right subtree. This
method is suitable for creating a copy of the
tree or evaluating expressions in prefix form.
Example order: A, B, D, E, C, F.

7. Depth-First Traversal
üInorder Traversal (Left – Root – Right): The left subtree is visited first,
followed by the root node, and finally the right subtree. In a Binary Search
Tree (BST), this traversal produces data in ascending order, making it useful
for sorting and data searching.
üPostorder Traversal (Left – Right – Root): The left subtree is visited first,
then the right subtree, and finally the root node. This method is used in
operations that require processing child nodes before the parent, such as tree
deletion or postfix expression evaluation.

8. Breadth-First Traversal
This traversal visits nodes level by level,
starting from the root node (level 0), then
all nodes at the next level from left to right.
It is typically implemented using a queue.
BFT is widely used in shortest path
algorithms, tree height calculation, and
tree structure visualization.

9. Importance of Tree Traversal
The Importance of Tree Traversal in Data Structures:
1.Systematic Data Processing: Provides a structured way to access and
manipulate each node.
2.Foundation for Advanced Algorithms: Traversal serves as the basis for
algorithms in binary search trees, AVL trees, mathematical expression
parsing, and pathfinding.
3.Performance Optimization: Choosing the right traversal method can
enhance the efficiency of searching, storing, and manipulating data across
various applications.

10. Application of Tree Traversal
1.Data Structures and File Systems: Tree traversal is used to explore the
hierarchical structure of folders and files; pre-order traversal displays the
creation order, while post-order traversal is useful for recursive deletion.
2.Database Indexing and Searching: Tree structures such as B-Trees and B+
Trees utilize traversal for data searching and manipulation; in-order traversal
ensures ordered data retrieval to accelerate queries.

11. Application of Tree Traversal
3.Compilation and Expression Parsing: The Abstract Syntax Tree (AST)
represents the syntactic structure of a program; post-order traversal is used
to evaluate arithmetic expressions, while pre-order traversal is used to
generate machine code.
4.Artificial Intelligence and Game Development: Search trees and decision
trees use traversals such as DFS and BFS to explore game moves, plan paths,
and make decisions in AI algorithms.

12. Application of Tree Traversal
5.Data Compression and Processing: The Huffman Coding algorithm uses tree
traversal to generate optimal binary codes; pre-order traversal constructs the
code table, while post-order traversal is used for decompression.
6.Computer Networks and Routing: Traversal on a spanning tree ensures data
distribution without loops, while Kruskal’s and Prim’s algorithms utilize tree
traversal to form optimal network paths.
7.Data Science and Machine Learning: Traversal is used in Decision Trees
and Random Forests to trace nodes from root to leaf, enabling systematic
classification and prediction based on conditions at each node.

13. Department of Informatics
Faculty of Industrial Engineering
Universitas Pembangunan Nasional “Veteran” Yogyakarta
Andi Nurkholis, S.Kom., M.Kom.
November 17, 2025
Done
Thank
You