Tree Traversal – Preorder, Inorder, Postorder

Traversing a Tree is done to visit each and every node of the tree. Since from a given node, there is more than one possible next node(more than one children) and we are performing sequential access/traversal (not parallel), some nodes must be deferred(stored for visiting later). This is often done via a stack (LIFO) data structure and using preorder or postorder or inorder methods.

Various Methods for Tree Traversal are

1. Preorder
2. Inorder
3. Postorder

Preorder Traversal

(root, left, right)

1. Visit the root element & print it.
2. Visit the left subtree by recursively calling preorder function.
3. Visit the right subtree by recursively calling preorder function.

Algorithm

int preorder(tree){
    if(tree == NULL)
        return 0;
    
    print(tree->data);
    preorder(tree->left);
    preorder(tree->right);
    
    return 0;
}

Inorder Traversal

(left, root, right)

1. Visit the left subtree by recursively calling inorder function.
2. Visit the root element & print it.
3. Visit the right subtree by recursively calling inorder function.

Algorithm

int inorder(tree){
    if(tree == NULL)
        return 0;
    
    print(tree->data);
    inorder(tree->left);
    inorder(tree->right);
    
    return 0;
}

Postorder Traversal

(left, right, root)

1. Visit the root element & print it.
2. Visit the left subtree by recursively calling preorder function.
3. Visit the right subtree by recursively calling preorder function.

Algorithm

int postorder(tree){
    if(tree == NULL)
        return 0;
    
    postorder(tree->left);
    postorder(tree->right);
    print(tree->data);
    
    return 0;
}

CPP code for Tree Traversal

#include<bits/stdc++.h>
using namespace std;

class Node{
	
	public:
    Node *lchild,*rchild;
    int data;
	
	public:
		Node(int x){
			data = x;
			lchild = NULL;
			rchild = NULL;
		}
};

int preorder(Node *tree){
	if(tree == NULL)
		return 1;

	cout<<tree->data<<" ";
	preorder(tree->lchild);
	preorder(tree->rchild);

	return 1;
}

int inorder(Node *tree){
	if(tree == NULL)
		return 1;

	inorder(tree->lchild);
	cout<<tree->data<<" ";
	inorder(tree->rchild);

	return 0;
}

int postorder(Node *tree){
	if(tree == NULL)
		return 1;

	postorder(tree->lchild);
	postorder(tree->rchild);
	cout<<tree->data<<" ";

	return 0;
}

int main(){

	Node *tree = new Node(5);

	tree->lchild = new Node(3);
	tree->lchild->lchild = new Node(2);
	tree->lchild->rchild = new Node(4);

	tree->rchild = new Node(8);
	tree->rchild->lchild = new Node(6);
	tree->rchild->rchild = new Node(9); 

	cout<<"Preorder Traversal of the Tree is: ";
	preorder(tree);
	cout<<endl;

	cout<<"Inorder Traversal of the Tree is: ";
	inorder(tree);
	cout<<endl;

	cout<<"Postorder Traversal of the Tree is: ";
	postorder(tree);
	cout<<endl;

	return 0;
}

Input Tree:
                            5
                          /   \
                         3     8
                       /  \   /  \
                      2    4  6   9

Output:
Preorder Traversal of the Tree is: 5 3 2 4 8 6 9
Inorder Traversal of the Tree is: 2 3 4 5 6 8 9
Postorder Traversal of the Tree is: 2 4 3 6 9 8 5

The time complexity all of the tree traversal algorithm(Preorder, Inorder, Postorder) is O(N), N is the number of nodes in the tree.