Tree traversal refers to the process of visiting or accessing each node of a tree exactly once in a specific order.
There're many familiar algorithms that are frequently seen in problem solving.
DFS(Depth-First Search)
- Explores as far as possible along a branch before exploring the next branch.
- Types: Inorder, Preorder, Postorder
BFS(Breadth-First Search)
- Explores nodes level by level from top to bottom.
- Type: Level Order Traversal
Inorder Traversal
Inorder traversal visits the node in the order: Left -> Root -> Right
Uses of Inorder Traversal
- In the case of BST(Binary Search Tree), Inorder traversal gives nodes in the non-decreasing order.
- To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed can be used.
- Inorder traversal can be used to evaluate arithmetic expressions stored in expression tree.
Preorder Traversal
Preorder traversal visits the node in the order: Root -> Left -> Right
Uses of Preorder Traversal
- Preorder traversal is used to create a copy of the tree.
- Preorder traversal is also used to get prefix expressions on an expression tree.
Postorder Traversal
Postorder traversal visits the node in the order: Left -> Right -> Root
Uses of Postorder Traversal
- Postorder traversal is used to delete the tree.
- Postorder traversal is also useful to get the prefix expression of an expression tree.
- Postorder traversal can help in garbage collection algorithms, particularly in systems where manual memory management is used.