A Tree which is a hierarchical (non-linear) data structure can be traversed in multiple ways unlike the linear data structure eg array, linked list etc which can be traversed only in a single linear way.
The basic two ways using which we can traverse a tree are:
- Depth First Traversal
- Inorder
- Preorder
- Postorder
- Breadth First Traversal
So let’s talk about all form of depth-first traversal i.e inorder, preorder and postorder.
Inorder Traversal
- Left subtree.
- Root.
- Right subtree.
In this approach, we first go the left subtree of the tree then back to the root and after that to the right subtree of the tree.
Preorder Traversal
- Root.
- Left subtree.
- Right subtree.
In Preorder traversal method we start from the root, then we go the left subtree of the tree and finally to the right subtree.
Preorder Traversal
- Left subtree.
- Right subtree.
- Root.
In Postorder tree traversal method we first visit the left subtree and then the right subtree and finally the root.
To implement these traversal methods we will use recursion because each part of the tree whether left or right is itself a tree (i.e subtree) so with recursion, we can easily treat each node as the root of the underlying subtree.
Trick: Whichever method you use always remember that left subtree always comes before the right subtree.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
class Node{ int value; Node left; Node right; //Constructor to initialize value to node Node(int value){ this.value = value; left = right = null; } //Function to insert data i.e to form binary tree public void insert(int v){ if(v < value){ if(left == null){ left = new Node(v); } else { left.insert(v); } } else { if(right == null){ right = new Node(v); } else{ right.insert(v); } } } //Function to perform Pre-Order Travesal public void preOrder(){ //1. Root System.out.print(value+" "); //2. Left subtree if(left != null){ left.preOrder(); } //3. Right subtree if(right != null){ right.preOrder(); } } //Function to perform Post-Order Travesal public void postOrder(){ //1. Left subtree if(left != null){ left.postOrder(); } //2. Right subtree if(right != null){ right.postOrder(); } //3. Root System.out.print(value+" "); } //Function to perform In-Order Travesal public void inOrder(){ //1. Left subtree if(left != null){ left.inOrder(); } //2. Root System.out.print(value+" "); //3. Right subtree if(right != null){ right.inOrder(); } } } class Main { public static void main(String[] args) { Node root = new Node(25); root.insert(20); root.insert(31); root.insert(19); root.insert(23); root.insert(26); root.insert(36); System.out.print("\n Inorder: "); root.inOrder(); System.out.print("\n Preorder: "); root.preOrder(); System.out.print("\n Postorder: "); root.postOrder(); } } |
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include <iostream> using namespace std; //Class TreeNode represent each node class TreeNode{ public: int data; TreeNode *leftNode {nullptr}; TreeNode *rightNode {nullptr}; TreeNode(); TreeNode(int d); void insertData(int d); void inorderTraverse(); void preorderTraverse(); void postorderTraverse(); }; //Implementing TreeNode class prototypes function. TreeNode::TreeNode(int d){ data = d; } //Inserting node as a left child if it is smaller than the current node //else it will be inserted as the right child // Assuming no two numbers/nodes are same void TreeNode::insertData(int d){ if(d < data){ if(leftNode == nullptr){ leftNode= new TreeNode(d); } else { leftNode->insertData(d); } } else { if(rightNode == nullptr){ rightNode = new TreeNode(d); } else { rightNode->insertData(d); } } } // Inorder traversal algorithm void TreeNode::inorderTraverse(){ //1.Left subtree if(leftNode != nullptr){ leftNode->inorderTraverse(); } //2. Root cout << data << " "; //3. Right subtree if(rightNode != nullptr){ rightNode->inorderTraverse(); } } // Preorder traversal algorithm void TreeNode::preorderTraverse(){ //1. Root cout << data << " "; //2.Left subtree if(leftNode != nullptr){ leftNode->preorderTraverse(); } //3. Right subtree if(rightNode != nullptr){ rightNode->preorderTraverse(); } } // Postorder Traversal Algorithm void TreeNode::postorderTraverse(){ //1.Left subtree if(leftNode != nullptr){ leftNode->postorderTraverse(); } //2. Right subtree if(rightNode != nullptr){ rightNode->postorderTraverse(); } //3. Root cout << data << " "; } int main() { //Taking root node as 25 TreeNode *root= new TreeNode(25); //inserting data into the binary tree root->insertData(20); root->insertData(31); root->insertData(19); root->insertData(23); root->insertData(26); root->insertData(36); //Calling inorder traversal function from root object cout << "\n Inorder: "; root->inorderTraverse(); cout << "\n Preorder: "; root->preorderTraverse(); cout << "\n Postorder: "; root->postorderTraverse(); return 0; } |
Output
|
1 2 3 |
Inorder: 19 20 23 25 26 31 36 Preorder: 25 20 19 23 31 26 36 Postorder: 19 23 20 26 36 31 25 |
In the above program, we have used the node as a class and inserted values (other nodes) using the root node. By doing this we form a Binary tree, then traversed it using the tree traversal method.
If you have any doubts or suggestion then comment below.