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.

Tree traversal is the process of visiting each node in a tree data structure exactly once in a specific order. It is mainly used in binary trees to access or process data systematically. The three main types of depth-first traversal are Pre-order, In-order, and Post-order. In Pre-order traversal, we visit the root node first, then the left subtree, and then the right subtree. In In-order traversal, we visit the left subtree first, then the root node, and finally the right subtree. This method is useful in binary search trees because it gives values in sorted order. In Post-order traversal, we visit the left subtree, then the right subtree, and finally the root node. The main difference between these methods is the position of the root node: in Pre-order it comes first, in In-order it comes in the middle, and in Post-order it comes at the end. These traversal techniques are widely used in searching, printing tree data, evaluating expressions, and deleting nodes in a tree.