Preorder Tree Traversal (DFS) in java
Traversing of tree has different approach than that of linear data structures (Array, Linked List, Queues, Stacks, etc).
There are different ways to traversal a tree in DFS such as:
Here in this article, we shall discuss steps and different approach of implementing Preorder tree traversal.
Steps for Preorder Tree Traversal are :
1) Visit the root.
2) Traverse the left subtree, i.e., call Preorder(left-subtree)
3) Traverse the right subtree, i.e., call Preorder(right-subtree) 
Preorder Traversal of above tree is 10, 20, 40, 70, 50, 30, 60
Time Complexity: O(n)
There are two ways to implement Preorder Tree Traversal.
1) Recursive
2) Iterative
Recursive solution for Preorder Tree Traversal :
Recursive solution for Preorder Traversal is similar to the steps we had discussed above. Algorithm for recursive solution is
|
1 2 3 |
1) Print root node 2) Traversal left node i.e preorder(root.left) 3) Traversal right node i.e preorder(root.right) |
Code for recursive solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
package com.code2succeed.tree; public class PreorderTraversal { public static class Node { private int data; private Node left; private Node right; public Node(int data) { this.data = data; } } public void preorder(Node root) { if(root != null) { //print root node System.out.print(root.data+" "); //Traversal left preorder(root.left); //Traversal right preorder(root.right); } } public static void main(String[] args) { Node root = new Node(10); Node node20 = new Node(20); Node node30 = new Node(30); Node node40 = new Node(40); Node node50 = new Node(50); Node node60 = new Node(60); Node node70 = new Node(70); root.left = node20; root.right = node30; node20.left = node40; node20.right = node50; node40.left = node70; node30.right = node60; PreorderTraversal pt = new PreorderTraversal(); pt.preorder(root); } } |
Output
|
1 |
10 20 40 70 50 30 60 |
Iterative solution for Preorder Traversal
To implement iterative solution for preorder Traversal, we will be using Stack data structure.Algorithm for iterative solution is
|
1 2 3 4 5 |
1) Push the root to the stack 2) while stack is not empty do the following - pop the top node and print it. - push the right node of the popped node to the stack. - push the left node of the popped node to the stack. |
Code for iterative solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
package com.code2succeed.tree; import java.util.Stack; public class PreorderTraversal { public static class Node { private int data; private Node left; private Node right; public Node(int data) { this.data = data; } } public void preorderIterative(Node root) { if(root == null) { return; } Stack<Node> stack = new Stack<Node>(); stack.push(root); while(!stack.isEmpty()) { Node top = stack.pop(); System.out.print(top.data+" "); if(top.right != null) { stack.push(top.right); } if(top.left != null) { stack.push(top.left); } } } public static void main(String[] args) { Node root = new Node(10); Node node20 = new Node(20); Node node30 = new Node(30); Node node40 = new Node(40); Node node50 = new Node(50); Node node60 = new Node(60); Node node70 = new Node(70); root.left = node20; root.right = node30; node20.left = node40; node20.right = node50; node40.left = node70; node30.right = node60; PreorderTraversal pt = new PreorderTraversal(); pt.preorderIterative(root); } } |
Output
|
1 |
10 20 40 70 50 30 60 |
Download code for Preorder Tree Traversal
Stay tuned for more updates and tutorials !!!