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
- Preorder
- Inorder
- Postorder
Preorder Traversal
(root, left, right)
- Visit the root element & print it.
- Visit the left subtree by recursively calling preorder function.
- 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)
- Visit the left subtree by recursively calling inorder function.
- Visit the root element & print it.
- 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)
- Visit the root element & print it.
- Visit the left subtree by recursively calling preorder function.
- 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.