There are multiple ways to in which you can traverse a tree. In this article we will see these traversals in detail. If you are new to trees then I would recommend that you pay close attention to this article because you will be solving almost all the problems on tree by using one or more of these traversals.
Here we will discuss the recursive approach, we will have separate posts for Iterative or Non-recursive approach.
Traversals:
- Preorder
- Inorder
- Postorder
- Breadth First Search(BFS) or Level order traversals
- Depth First Search(DFS).
In every traversal we visit the tree in certain order. lets discuss them in detail.
Preorder Traversal: ( Read about non-recursive approach of Preorder Traversal)
- Visit the root.
- Visit the left-subtree.
- Visit the right-subtree.
Inorder Traversal: ( Read about non-recursive approach of Inorder Traversal)
- Visit the left-subtree.
- Visit the root.
- Visit the right-subtree.
Postorder Traversal: ( Read about non-recursive approach of Postorder Traversal)
- Visit the right-subtree.
- Visit the left-subtree.
- Visit the root.
Click here to read about Breadth-First Search and Depth-First Search.
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class TreeTraversals { | |
| public void inorderRecursive(Node root) { | |
| if (root != null) { | |
| inorderRecursive(root.left); | |
| System.out.print(root.data + " "); | |
| inorderRecursive(root.right); | |
| } | |
| } | |
| public void postOrderRecursive(Node root) { | |
| if (root != null) { | |
| postOrderRecursive(root.right); | |
| postOrderRecursive(root.left); | |
| System.out.print(root.data + " "); | |
| } | |
| } | |
| public void preOrderRecursive(Node root) { | |
| if (root != null) { | |
| System.out.print(root.data + " "); | |
| preOrderRecursive(root.left); | |
| preOrderRecursive(root.right); | |
| } | |
| } | |
| public static void main(String[] args) { | |
| Node root = new Node(1); | |
| root.left = new Node(2); | |
| root.right = new Node(3); | |
| root.left.left = new Node(4); | |
| root.left.right = new Node(5); | |
| root.right.left = new Node(6); | |
| root.right.right = new Node(7); | |
| TreeTraversals i = new TreeTraversals(); | |
| System.out.println("Inorder Traversal:"); | |
| i.inorderRecursive(root); | |
| System.out.println("\nPreorder Traversal:"); | |
| i.preOrderRecursive(root); | |
| System.out.println("\nPostorder Traversal:"); | |
| i.postOrderRecursive(root); | |
| } | |
| } | |
| class Node { | |
| int data; | |
| Node left; | |
| Node right; | |
| public Node(int data) { | |
| this.data = data; | |
| } | |
| } |
Output: Inorder Traversal:4 2 5 1 6 3 7 Preorder Traversal:1 2 4 5 3 6 7 Postorder Traversal:7 6 3 5 4 2 1
As per the explanation ,it seems that the code for postOrderRecursive is not right ,it visit right subtree firstly.
Thanks Fuen, changed the explanation.
Post order traversal Algorithm is not correct.
It should be as follows-
1. Visit the left subtree
2. Visit the right subtree.
3. Then visit the root
+1, Fuen Wu propably meant that the code is wrong, the correct order of Post order indeed is Left Right Root.