[Tree traversal](https://www.educative.io/answers/what-is-tree-traversal) means visiting all the nodes of a tree exactly once. Visiting can be interpreted as doing something to the node, for example, printing the value contained in it. 

**Pre-order** traversal is one of the many ways to traverse a tree. It is mainly used when a tree needs to be duplicated.

# Basic Algorithm

The following algorithm is specific to a [binary tree](https://www.educative.io/answers/what-is-a-binary-search-tree) but can be generalized​ to an n-ary tree (a tree where each node can have at most​ n children nodes).

1. Visit the root
2. Recursively traverse the left subtree
3. Recursively traverse the right subtree

For an n-ary tree:
1. Visit the root node
2. Traverse the subtrees recursively from left to right

# Example

The following code snippet implements pre-order traversal for a binary tree.

#include <iostream>
using namespace std;

struct Tree
{
	char data;
	Tree *left;
	Tree *right;
  Tree(char data) 
    { 
        this -> data = data; 
        left = NULL;
        right = NULL; 
    }     
};
void PreOrderTraversal(Tree *node)
{
	if(node == NULL){
    return;
  }
  else{
    cout << node -> data << ", ";
    PreOrderTraversal(node -> left);
    PreOrderTraversal(node -> right);
  } 
}
int main() {
  Tree *root = new Tree('a'); 
  root -> left = new Tree('b'); 
  root -> right = new Tree('c'); 
  root -> left -> left = new Tree('d'); 
  root -> left -> left -> left = new Tree('e');
  root -> left -> left -> right = new Tree('f');  
  PreOrderTraversal(root);
  return 0;
}

What is pre-order traversal?

Basic Algorithm

Example