# Data Structures - Tree Traversal

- Tree traversal is the action of visiting all the nodes in the tree exactly once.
- There are three ways to traverse a tree.
- In-Order Traversal
- Pre-Order Traversal
- Post-Order Traversal

- Primary purpose of tree traversal is to search and locate an item in the tree

### In-Order Traversal

In In-order traversal, the left nodes are traversed first, then the root node and then the right nodes.

We traverse the left subtree recursively by calling In-Order function, then process the root node, and then traverse the right subtree recursively by calling In-Order function.

The output of the above tree is.

` D-->B-->E-->A-->F-->C `

### Pre-Order Traversal

In Pre-Order traversal, the root node is visited first, then the left subtree and right subtree are traversed.

Here we first process the root, then traverse the left subtree recursively by calling Pre-Order function, and traverse the right subtree recursively by calling Pre-Order function.

The output of the above tree is

` A-->B-->D-->E-->C-->F `

### Post-Order Traversal

In Post-Order traversal, we will first traverse the left nodes, then the right nodes and then traverse the root node.

We traverse the left subtree recursively by calling Post-Order function, then traverse the right subtree recursively by calling Post-Order function and finally process the root node.

The output of the above tree is.

` D-->E-->B-->F-->C-->A `