#include <iostream>
using namespace std;
class Node {
public :
string data;
Node *left;
Node *right;
Node(string value) {
data = value;
left = NULL;
right = NULL;
}
};
class TreeTraversal {
public :
Node *root;
TreeTraversal() {
root = NULL;
}
void preorder(Node *node) {
if (node != NULL) {
cout << node->data << " ";
preorder(node->left);
preorder(node->right);
}
}
void postorder(Node *node) {
if (node != NULL) {
postorder(node->left);
postorder(node->right);
cout << node->data << " ";
}
}
void inorder(Node *node) {
if (node != NULL) {
inorder(node->left);
cout << node->data << " ";
inorder(node->right);
}
}
};
int main() {
TreeTraversal treeTraversal;
treeTraversal.root = new Node("A");
treeTraversal.root->left = new Node("B");
treeTraversal.root->right = new Node("C");
treeTraversal.root->left->right = new Node("D");
treeTraversal.root->right->left = new Node("E");
cout << "Preorder traversal : " << endl;
treeTraversal.preorder(treeTraversal.root);
cout << endl << endl;
cout << "Postorder traversal : " << endl;
treeTraversal.postorder(treeTraversal.root);
cout << endl << endl;
cout << "Inorder traversal : " << endl;
treeTraversal.inorder(treeTraversal.root);
}
So, in this case we have taken the below Tree and and calculated the Preorder, Postorder and Inorder Traversal for the below Tree.
Just remember, we have used a process called Recursion. Where C++ maintains an internal Stack to remember the visited Nodes. So, that the Nodes are not visited twice.
So, we have a Node class,
class Node {
public :
string data;
Node *left;
Node *right;
Node(string value) {
data = value;
left = NULL;
right = NULL;
}
};To understand the Node class, let us take any Node and understand it in detail.
Let us take the Node A as example.
So, the Node A has a name i.e A. A Left part that should hold the Left Node i.e. B and a Right part to hold the Right Node i.e. C.
Now, if you look at the Node class. It has string type attribute string data to hold name of the Node i.e. A.
There is also a Node type attribue Node left that holds the left Node of A, i.e. B and there is a Node type attribue Node right that holds the right Node of A, i.e. C.
So, Node A looks somewhat like,
Now, let us see the Tree Traversal in action.
So, at first we construct the Tree,
treeTraversal.root = new Node("A");
treeTraversal.root->left = new Node("B");
treeTraversal.root->right = new Node("C");
treeTraversal.root->left->right = new Node("D");
treeTraversal.root->right->left = new Node("E");And there is the constructor in the Node class that helps us create the Nodes.
Node(string value) {
data = value;
left = NULL;
right = NULL;
}And the tree is constructed,
Next, we start the Preorder Traversal,
treeTraversal.preorder(treeTraversal.root);
And the preorder(Node node) method is called, and just remember that we are passing the root Node to the method.
void postorder(Node *node) {
if (node != NULL) {
postorder(node->left);
postorder(node->right);
cout << node->data << " ";
}
}Although, the lines of code looks very less. It is because, the recursion process is doing a lot for us. And it all happens internally, hidden from us.
Let us understand the process in detail.
So, the root Node is A and the node variable has the details of Node A in it.
In the first line we perform a null check
if (node != NULL)
And then begin the Preorder Traversal. And the rule is Root --> Left --> Right.
i.e. We visit the root element first, then visit all the elements of the Left Sub-Tree and finally, visit all the elements of the Right Sub-Tree.
So, as per the rule we will visit the root Node A and print it first.
cout << node->data << " ";
So, the result is :
A
Then we are suppose to visit all the elements of the Left Sub-Tree. And thus we call the preorder(...) method from itself, by passing the Left Node i.e. B (As node.left contains B).
preorder(node.left);
Now, the preorder(...) method is called again. And this time Node B becomes the new root element.
And once again the same method is executed with Node B.
void preorder(Node *node) {
if (node != NULL) {
cout << node->data << " ";
preorder(node->left);
preorder(node->right);
}
}Even in this case, as per the Preorder traversal process Root --> Left --> Right. We print the new root element B.
cout << node->data << " ";
So, the result is :
A B
And once again we call the preorder(...) method.
preorder(node->left);
And this time node.left is NULL. Because B has no left element.
So, preorder(...) method is called with the new root element as NULL.
void preorder(Node *node) {
if (node != NULL) {
cout << node->data << " ";
preorder(node->left);
preorder(node->right);
}
}And this time node variable is NULL. So, the method execution ends here.
if (node != NULL)
But! Just Hold on!
The program execution has not yet ended. This is the time when C++ starts backtracking.
Don't get scared by the word backtracking. We will understand it eventually.
Now, just think! The method execution in the above case was not completed. i.e. The line preorder(node.right) never got executed. Well! C++ also remembers it.
And C++ does a time travel and goes back to the time when the method executed with Node B.
void preorder(Node *node) {
if (node != NULL) {
cout << node->data << " ";
preorder(node->left);
preorder(node->right);
}
}
And executes the unfinished line,
preorder(node->left);
And this time preOrder(...) method is called with Node D.
And same way, Node D would be printed.
cout << node->data << " ";
So, the result is :
A B D
And since, there are no children of Node D. It is time to complete the unfinished execution, i.e. When Node A was the root element.
void preorder(Node *node) {
if (node != NULL) {
cout << node->data << " ";
preorder(node->left);
preorder(node->right);
}
}And we come to the unfinished line of preorder(...) method.
i.e.
preorder(node->right);
And think logically, we are done with the root element A. Also we are done traversing all the elements of the Left Sub-Tree B. And now, it's time for us to traverse the Right Sub-Tree C.
So, this time the method preorder(...) is called with the root Node C.
void preorder(Node *node) {
if (node != NULL) {
cout << node->data << " ";
preorder(node->left);
preorder(node->right);
}
}
Since the root Node is C. So, we print C.
cout << node->data << " ";
So, the result is :
A B D C
Then the preOrder(...) method is called with E as root(Since, E is the left child of C).
preorder(node->left);
And the method is called again printing C.
A B D C E
And finally, all the elements are visited and with this we complete the Preorder traversal.
And exactly the same execution pattern follows for the methods :