Tree Traversals
2 min readJan 22, 2021
Traversing A Binary Tree
- Traversing a binary tree is the process of visiting each and every node in the tree exactly once in a systematic way.
- As we know that a tree is a non-linear data structure in which the elements can be traversed in many different ways.
- Types of traversals
- Pre-order Traversal
- In-order Traversal
- Post-order Traversal
Pre-order Traversal:-
- To traverse a nonempty binary tree in pre-order, the following operations are performed at each node:
- Visiting the root node,
- Traversing the left sub-tree,
- Traversing the right sub-tree.
Pre-order Traversal: 1 2 4 3 5 7 8 6
- The pre-order traversal of the above tree is 1–2–4–3–5–7–8–6 as we have to traverse from root first, and then left sub-tree, and finally right sub-tree.
- Pre-order traversal is also called depth-first traversal.
- The word ‘pre’ in the pre-order specifies that the root node is traversed first to any other nodes in the left and right sub-trees.
C++ code for pre-order traversal
//recursive function to perform pre-order traversal of the tree
void preorder(struct node *root)
{
//if the current node is empty
if(root==NULL)
return;
//display the data part of the root node.
cout<<root->data;
//traverse the left sub-tree
preorder(root->left);
//traverse the right sub-tree
preorder(root->right);
}
In-order Traversal:
- To traverse a nonempty binary tree in in-order, the following operations are performed at each node:
- Traversing the left sub-tree,
- Visiting the root node,
- Traversing the right sub-tree.
In-order Traversal: 4 2 1 7 5 8 3 6
- The in-order traversal of the above tree is 4–2–1–7–5–8–3–6.
- Left sub-tree first, and then root node, and finally the right sub-tree.
- In-order traversal is also called symmetric traversal.
- The word ‘in’ in the in-order…