Binary Tree Traversal
 Binary Tree Traversal
 Binary Tree Traversal Illustration
 Binary Tree Traversal Algorithm
 Binary Tree Traversals Implementation
 Binary Tree Traversal Algorithm Complexity
A Binary Tree is a nonlinear data structure. It is called a binary tree because each node has a maximum of two children. These children are called left children and right children. It can also be interpreted as an undirected graph in which the topmost node is called root. Unlike linear data structures that can only be traversed in only one way, a tree can be traversed in different ways. We can traverse a tree by exploring along the depth or the breadth. The first approach is called the DepthFirst Traversal, and the second is called the BreadthFirst Traversal. In this article, we will discuss the DepthFirst Traversals.
There are 3 kinds of depthfirst traversals  inorder, preorder, and postorder. We will discuss each of them one by one.
Binary Tree Traversal
Inorder Traversal
In this traversal, we first visit the left subtree, then the root, and lastly the right subtree. Every node resembles a subtree. For BST, inorder traversal returns all the elements in ascending order
Preorder Traversal
In this traversal, we first visit the root, then the left subtree, and lastly the right subtree. Every node resembles a subtree. It is normally used to replicate, i.e., create a copy of the tree. Prefix traversal also helps to generate prefix expression from an expression tree.
Postorder Traversal
In this traversal, we first visit the left subtree, then the right subtree, and lastly the root. Every node resembles a subtree. It is used to delete trees effectively. It also helps to generate postfix expression from an expression tree.
Binary Tree Traversal Illustration
Inorder Traversal: (4, 2, 1, 5, 3, 6, 7, 8, 9)
We call inorder traversal on root node 3
. Recursively traverse left to reach node 4
, which is the leftmost node, and include it in our output; as it is the root and has no left node, we visit its rightmost node 2
and include it in our traversal. In this way, we traverse the whole tree to get the above order as our output.
Preorder Traversal: (3, 1, 4, 2, 5, 7, 6, 9, 8)
We call preorder traversal on root node 3
and include it in our output. Then we recursively traverse left to reach the next root node 1
and then subsequently 4
. Since 4
has no left child, we visit the right node 2
. Now we have covered the subtree under the root node 4
and we trace back to node 1
and go towards its right to node 5
. This way, we traverse the whole tree to get the above order as our output.
Postorder Traversal: (2, 4, 5, 1, 6, 8, 9, 7, 3)
We call postorder traversal on root node 3
.Recursively traverse left to reach node 4
. Before including 4
in our traversal, we have to visit its right node 2
. We include 2
and then 4
in our output and move back to 1
.1
has its right node 5
unvisited, so we first include 5
and then 1
in output. Then we trace back to root node 3
and proceed with traversing the right subtree. This way, we traverse the whole tree to get the above order as our output.
Binary Tree Traversal Algorithm
Inorder Traversal

Traverse the left subtree by recursively calling the inorder function.

Visit the root node.

Traverse the right subtree by recursively calling the inorder function.
Preorder Traversal

Visit the root node.

Traverse the left subtree by recursively calling the inorder function.

Traverse the right subtree by recursively calling the inorder function.
Postorder Traversal

Traverse the left subtree by recursively calling the inorder function.

Traverse the right subtree by recursively calling the inorder function.

Visit the root node.
Binary Tree Traversals Implementation
#include <iostream>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
Node(int x) {
this>key = x;
this>left = this>right = NULL;
}
};
void inorder(Node* root) {
if (root != NULL) {
inorder(root>left);
cout << root>key << " ";
inorder(root>right);
}
}
void preorder(Node* root) {
if (root != NULL) {
cout << root>key << " ";
preorder(root>left);
preorder(root>right);
}
}
void postorder(Node* root) {
if (root != NULL) {
postorder(root>left);
postorder(root>right);
cout << root>key << " ";
}
}
int main() {
Node* root = new Node(3);
root>left = new Node(1);
root>right = new Node(7);
root>left>left = new Node(4);
root>left>right = new Node(5);
root>left>left>right = new Node(2);
root>right>left = new Node(6);
root>right>right = new Node(9);
root>right>right>left = new Node(8);
cout << "The inorder traversal of the tree is : ";
inorder(root);
cout << endl;
cout << "The preorder traversal of the tree is : ";
preorder(root);
cout << endl;
cout << "The postorder traversal of the tree is : ";
postorder(root);
cout << endl;
}
Binary Tree Traversal Algorithm Complexity
Time Complexity
 Average Case
There are n
nodes in a tree, in all 3
kinds of traversals, we have to go and visit each node. Since we iterate over n
nodes, although in a different order, the time complexity for all 3 traversals is the order of O(n)
. The averagecase time complexity is O(n)
.
 Best Case
The bestcase time complexity is O(n)
. It is the same as averagecase time complexity for all the 3
traversals.
 Worst Case
The worstcase time complexity is O(n)
. It is the same as worstcase time complexity for all the 3
traversals.
Space Complexity
The algorithm’s space complexity is O(n)
due to the extra space required by recursion calls.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedInRelated Article  Data Structure
 Circular Doubly Linked List
 Circular Linked List
 Doubly Linked List
 Linked List Deletion
 Linked List Insertion
 Linked List Merge Sort