In this blog post we will investigate four key algorithms used to read through the content of a binary tree:
- Breadth-First Traversal Algorithm
- Depth-First Algorithms:
- Pre-Order Traversal
- In-Order Traversal
- Post-Order Traversal
Binary Tree?
A Binary Tree is a data structure used in some algorithms to store data. In a binary tree each node can have up to two children.
Breadth-First Traversal Algorithm
A Breadth-first traversal consists of accessing each node, one level after the ohter. On each layer the nodes are accessed as they appear, from left to right.
Depth-First Traversal Algorithms
There are three depth-first traversal agorithms which are all based on a recursive approach.
Pre-Order Traversal Algorithm:
|
1 2 3 4 5 6 7 |
FUNCTION preorder-traverse(tree) IF tree is not empty visit root node of tree preorder-traverse(left sub-tree) preorder-traverse(right sub-tree) END IF END FUNCTION |
In-Order Traversal Algorithm:
|
1 2 3 4 5 6 7 |
FUNCTION inorder-traverse(tree) IF tree is not empty inorder-traverse(left sub-tree) visit root node of tree inorder-traverse(right sub-tree) END IF END FUNCTION |
Post-Order Traversal Algorithm:
|
1 2 3 4 5 6 7 |
FUNCTION postorder-traverse(tree) IF tree is not empty postorder-traverse(left sub-tree) postorder-traverse(right sub-tree) visit root node of tree END IF END FUNCTION |
Binary Tree #1
 |
|
Binary Tree #2
 |
|
Binary Tree #3
 |
|
Binary Tree #4
 |
|
Flowchart Studio
Python Syntax