This post is also available in: العربية (Arabic)
A Binary Tree is a non-linear data structure. Thus, a binary tree can be traversed in more than one way. Let’s discuss different binary tree traversal in data structure kids should know.
Binary Tree Traversal in Data Structure
Binary tree traversal in data structure can be done in three different ways and these are
- Preorder
- Inorder
- Postorder
Binary Tree Traversal in Data Structure – Preorder Traversal
In this method first of all root of a node is visited, then the left subtree(or left node), and lastly the right subtree(or right node). The process is repeated till all the nodes are visited. To understand the process, let’s consider the following binary tree.
In this binary tree, the value in root is 1. The first node to be visited is 1. Next is the left subtree. The left subtree is
Again according to a preorder method, first of all, the root (value 2) is visited, then the left node (value 4) is visited and then the right node(value 3) is visited. With this, all the nodes of the left subtree are visited.
After that right subtree is visited. The right subtree is
In this subtree, the root node(value 3) is visited first, followed by a left node(value 6) and finally the right node(value 7).
The order of nodes visited using the preorder traversal method is 1, 2, 4, 5, 3, 6, and 7.
Algorithm for Preorder Traversal
Until all nodes are traversed:
Step 1: Visit the root node.
Step 2: Recursively traverse the left subtree.
Step 3: Recursively traverse the right subtree.
Code for Preorder Traversal in C++
struct node {
int data;
struct node *left;
struct node *right;
};
void preorder(struct node *root) {
if (root != NULL) {
cout<<root->data<<" ";
preorder(root->left);
preorder(root->right);
}
}
int main() {
struct node *root = NULL;
cout<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);
return 0;
}
Binary Tree Traversal in Data Structure – Inorder Traversal
In this method first of all left subtree(or left node) is visited, then the root, and lastly the right subtree(or right node). The process is repeated till all the nodes are visited. To understand the process, let’s consider the following binary tree.
In this binary tree, the left subtree is
Again according to an inorder method, first of all, the left(value 4) is visited, then root(value 2) is visited and then the right node(value 5) is visited. With this, all the nodes of the left subtree are visited.
Next, the root(value 1) of the binary tree is visited.
After that right subtree is visited. The right subtree is
In this subtree, the left node(value 6) is visited first, followed by a root node(value 3) and finally the right node(value 7).
The order of nodes visited using the inorder traversal method is 4, 2, 5, 1, 6, 3, and 7.
Algorithm for Inorder Traversal
Until all nodes are traversed:
Step 1: Recursively traverse the left subtree.
Step 2: Visit the root node.
Step 3: Recursively traverse the right subtree.
Code for Inorder Traversal in C++
struct node {
int data;
struct node *left;
struct node *right;
};
void inorder(struct node *root) {
if (root != NULL) {
inorder(root->left);
cout<<root->data<<" ";
inorder(root->right);
}
}
int main() {
struct node *root = NULL;
cout<<"In-Order traversal of the Binary Search Tree is: ";
inorder(root);
return 0;
}
Binary Tree Traversal in Data Structure – Postorder Traversal
In this method first of all left subtree(or left node) is visited, then the right subtree(or right node), and lastly the root. The process is repeated till all the nodes are visited. To understand the process, let’s consider the following binary tree.
In this binary tree, the left subtree is
Again according to a postorder method, first of all, the left(value 4) is visited, then the right node(value 5) is visited and then the root(value 2) is visited. With this, all the nodes of the left subtree are visited.
Next, the right subtree is visited. The right subtree is
In this subtree, the left node(value 6) is visited first, followed by a right node(value 7) and finally the root node(value 3).
And finally, the root(value 1) of the binary tree is visited.
The order of nodes visited using the postorder traversal method is 4, 5, 2, 6, 7, 3, and 1.
Algorithm for Postorder Traversal
Until all nodes are traversed:
Step 1: Recursively traverse the left subtree.
Step 2: Recursively traverse the right subtree.
Step 3: Visit the root node.
Code for Postorder Traversal in C++
struct node {
int data;
struct node *left;
struct node *right;
};
void postorder(struct node *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout<<root->data<<" ";
}
}
int main() {
struct node *root = NULL;
cout<<"Post-Order traversal of the Binary Search Tree is: ";
postorder(root);
return 0;
}
What is a Binary Search Tree?
A Binary Search Tree(BST) is a binary tree in which all the nodes follow the following properties:
- The value of a key of the left subtree is less than the value of its root node’s key.
- The value of a key of the right subtree is greater than the value of its root node’s key.
In the above binary tree, if you pick any value, then the value of its left node is less and that of the right node is more.
What is the Use of Binary Search Tree?
A Binary Search Tree is used to sort the data. When a binary search tree is traversed in an inorder way, the elements visited will be in ascending order. Let’s traverse the above binary tree in an inorder fashion.
First of all the left subtree is visited. The left subtree is
First of all left node(value 1) is visited. Next root(value 3) is visited. And next, the right subtree is visited.
In this subtree, the first left node(value 4) is visited, followed by root(value 6), and the right node(value 7) is visited.
Now, all the nodes left subtree of the original binary tree is visited. Now the root node(value 8) is visited.
After visiting the root node, the right subtree is visited.
In this subtree, since there is no left node, hence, the root node(value 10) is visited, and then the right subtree(containing only 2 nodes).
Lastly, the left node(value 13) of the last subtree is visited followed by its root(value 14). (There is no right subtree or node in this subtree).
The result of the traversal is 1, 3, 4, 6, 7, 8, 10, 13, and 14 which are in ascending order.
