Tree: Traversal (PreOrder, InOrder, PostOrder)

Problem: What are the different ways of traversing a non-empty Tree?

Solution: Tree traversal can be divided into 2 major methods. First is Depth-First-Traversal and the second is Breadth-First-Traversal.

Depth-First-Traversal(DFT or DFS): The idea is to recursively keep visiting the nodes in the left branch. When all nodes are visited in the left branch, visit the right branch recursively and move backup. Think of each branch(left or right) as a sub-tree.

Breadth-First-Traversal(BFT or BFS): Here all the nodes at the same level are visited before visiting nodes at a lower level. See the post on Breadth First Tree Traversal for an implementation using a Queue.

There are 3 different ways of Depth-First-Traversal depending on when the root node is visited with respect to the children sub-trees.

1. Pre-Order Traversal: The root node is visited before visiting the children nodes/sub-trees.

Algorithm:
a. Visit root node
b. Recursively visit left sub-tree
c. Recursively visit right sub-tree


Code:

PreOrderTraversal(Node * node)
{
    if(node == NULL)
       return;
    printf("%d", node->data);
    PreOrderTraversal(node->left);
    PreOrderTraversal(node->right);
}

2. In-Order Traversal: The root node is visited before visiting the right sub-tree but after visiting the left sub-tree.

Algorithm:
a. Recursively visit left sub-tree
b. Visit root node
c. Recursively visit right sub-tree


Code:

PreOrderTraversal(Node * node)
{
    if(node == NULL)
       return;
    PreOrderTraversal(node->left);
    printf("%d", node->data);
    PreOrderTraversal(node->right);
}

3. Post-Order Traversal: The root node is visited after visiting the left sub-tree as well as the right sub-tree.

Algorithm:
a. Recursively visit left sub-tree
b. Recursively visit right sub-tree
c. Visit root node
Code:

PreOrderTraversal(Node * node)
{
    if(node == NULL)
       return;
    PreOrderTraversal(node->left);
    PreOrderTraversal(node->right);
    printf("%d", node->data);
}