01
Module 8: Tree Traversal
Tree traversal is the process of visiting every node in a tree exactly once. Traversal is important when printing, searching, evaluating, or copying tree structures.
For binary trees, the common traversal methods are:
| Traversal | Order |
|---|---|
| Preorder | Visit root, then left subtree, then right subtree. |
| Inorder | Visit left subtree, then root, then right subtree. |
| Postorder | Visit left subtree, then right subtree, then root. |
| Level order | Visit nodes level by level from left to right. |
Preorder Traversal
Preorder visits the root before its subtrees.
Root -> Left -> Right
This is useful when copying a tree or displaying a prefix expression.
Inorder Traversal
Inorder visits the left subtree first, then the root, then the right subtree.
Left -> Root -> Right
For a binary search tree, inorder traversal displays values in sorted order.
Postorder Traversal
Postorder visits both subtrees before the root.
Left -> Right -> Root
This is useful when deleting a tree or evaluating postfix expressions.
Level-Order Traversal
Level-order traversal visits nodes from top to bottom, moving left to right at each level. It is commonly implemented using a queue.
02