Preorder Tree Traversal (DFS) in java

# 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)

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) 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

```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

`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) 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

```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

`10 20 40 70 50 30 60`