Inorder Traversal vs Preorder Traversal

In this post, we will learn the difference between Inorder Traversal and Preorder Traversal in Java. This is a frequently asked question in Java interviews for beginners. Let's dive into it.

Difference between Inorder Traversal and Preorder Traversal in Java

Feature	Inorder Traversal	Preorder Traversal
Traversal Order	Inorder traversal follows the left-root-right order, i.e., it visits the left subtree, then the root node, and finally the right subtree.	Preorder traversal follows the root-left-right order, i.e., it visits the root node, then the left subtree, and finally the right subtree.
Recursive Approach	In inorder traversal, the left subtree is explored recursively before visiting the root node and the right subtree.	In preorder traversal, the root node is visited first, followed by recursive exploration of the left subtree and then the right subtree.
Example	Consider the binary tree:	Consider the binary tree:
	1	1
	/ \	/ \
	2 3	2 3
	/ \ / \	/ \ / \
	4 5 6 7	4 5 6 7
	Inorder traversal: [4, 2, 5, 1, 6, 3, 7]	Preorder traversal: [1, 2, 4, 5, 3, 6, 7]
Application	Inorder traversal is commonly used for binary search trees to retrieve the elements in sorted order.	Preorder traversal is used to create a copy of the binary tree or to get the prefix expression of an expression tree.
Complexity	The time complexity of inorder traversal is O(n), where n is the number of nodes in the binary tree.	The time complexity of preorder traversal is also O(n) for the same reason.

In summary, inorder traversal explores the left subtree first, then visits the root node, and finally explores the right subtree. On the other hand, preorder traversal visits the root node first, then explores the left subtree, and finally explores the right subtree. Both traversals have different applications and can be used depending on the requirements of the problem at hand.