33. Tree Traversal Algorithms

Traversal is the process of visiting every node in the tree exactly once. The three main depth-first traversals are defined by when the root node is visited relative to its children.

Let N be the Node, L be the Left Subtree, and R be the Right Subtree.

1. Inorder Traversal (L N R)

• Visit Left Subtree, then visit Node, then visit Right Subtree.
• Result: For a BST, Inorder traversal yields the elements in sorted order.

2. Preorder Traversal (N L R)

• Visit Node, then Left Subtree, then Right Subtree.
• Result: Used to create a copy of the tree or to get the tree's prefix expression.

3. Postorder Traversal (L R N)

• Visit Left Subtree, then Right Subtree, then visit Node.
• Result: Used to delete the tree (must delete children before deleting the parent) or for postfix expressions.