Traversal is a method of traversing all of a tree's nodes and printing their values. We always begin at the root (head) node since all nodes are connected by edges (links). That is, we cannot reach a node in a tree at random. We can cross a tree in three different ways.
- In-order Traversal
- Pre-order Traversal
- Post-order Traversal
Generally, we traverse a tree to search or locate a given item or key in the tree or to print all the values it contains.
In-order Traversal
- The left subtree is visited first, second by the root, and finally the right subtree in this traversal approach. Always keep in mind that any node could be a subtree in and of itself.
- The output of a binary tree traversed in order produces sorted key values in ascending order.
- We begin with A and move to its left subtree B using in-order traversal. In the same way, B is traversed in sequence. The process continues until all nodes have been visited. The output of this tree's in-order traverse will be
D → B → E → A → F → C → G
Algorithm
Until all nodes are traversed −Step 1 − Recursively traverse left subtree.Step 2 − Visit root node.Step 3 − Recursively traverse right subtree.
Pre-order Traversal
- In this traversal method, the root node is visited first, then the left subtree and finally the right subtree.
- Starting with A, we visit A first, then move to its left subtree B, following pre-order traversal. B is also visited in a pre-order manner. The process continues until all nodes have been visited. The output of this tree's pre-order traversal will be
A → B → D → E → C → F → G
Algorithm
Until all nodes are traversed −Step 1 − Visit root node.Step 2 − Recursively traverse left subtree.Step 3 − Recursively traverse right subtree.
Post-order Traversal
- In this traversal method, the root node is visited last, hence the name. First we traverse the left subtree, then the right subtree and finally the root node.
- We begin at A and proceed to the left subtree B using pre-order traversal. B is also traversed in the reverse order. The process continues until all nodes have been visited. The output of this tree's post-order traversal will be
D → E → B → F → G → C → A
Algorithm
Until all nodes are traversed −Step 1 − Recursively traverse left subtree.Step 2 − Recursively traverse right subtree.Step 3 − Visit root node.
