1. Traversal
– traversal is a process to visit
all the nodes of a tree and may print their values. There are three way which
we use to traversal a tree –
I.
In-order traversal
II.
Pre-order traversal
III.
Post-order traversal
i.
In-order
traversal –
·
In this traversal
method, the left sub tree is visited first, then the root and later the right Sub-tree.
·
We should always remember that every node may
represent a sub tree itself.
·
If a binary tree is
traversed in-order, the output will produce sorted key values in an ascending order.
·
We start from A, and following
in-order traversal, we move to its left sub tree B.
·
B is also traversed in-order.
·
The process goes on
until all the nodes are visited.
·
The output of in
order Traversal of this tree will be –
D → B → E → A → F → C → G
Algorithm
Until all nodes are
traversed −
Step
1 − Recursively
traverse left sub tree.
Step
2 − Visit root node.
Step
3 − Recursively
traverse right sub tree.