What is Tree Traversal? Explain Pre-order, In-order, and Post-order with Examples

a Tree Traversal is the process of visiting (reading or processing) each node in a tree data structure exactly once.

Unlike linear data structures (like Arrays or Linked Lists) which can only be read in one sequential logical way, trees are non-linear. Therefore, they can be traversed in multiple ways. The most common tree traversals are categorized under Depth-First Search (DFS), which includes three main methods:

1. Pre-order Traversal

2. In-order Traversal

3. Post-order Traversal

2. Pre-order Traversal (Root $\rightarrow$ Left $\rightarrow$ Right)

In a Pre-order traversal, the root node is visited first, followed by the left subtree, and finally the right subtree.

• Algorithm / Steps:

  1. Visit the Root node.

  2. Recursively traverse the Left subtree.

  3. Recursively traverse the Right subtree.

• Primary Application: It is used to create a "clone" or exact copy of the tree. It is also used to evaluate Prefix expressions.

3. In-order Traversal (Left $\rightarrow$ Root $\rightarrow$ Right)

In an In-order traversal, the left subtree is visited first, then the root node, and finally the right subtree.

• Algorithm / Steps:

  1. Recursively traverse the Left subtree.

  2. Visit the Root node.

  3. Recursively traverse the Right subtree.

• Primary Application: In a Binary Search Tree (BST), performing an In-order traversal always returns the values in sorted (ascending) order.

4. Post-order Traversal (Left $\rightarrow$ Right $\rightarrow$ Root)

In a Post-order traversal, the left subtree is visited first, then the right subtree, and the root node is visited at the very end.

• Algorithm / Steps:

  1. Recursively traverse the Left subtree.

  2. Recursively traverse the Right subtree.

  3. Visit the Root node.

• Primary Application: It is used to delete the tree from memory (because you must delete the children before you delete the parent node). It is also used to evaluate Postfix expressions.