# Depth First Search in Java

### Depth First Search [DFS]

It’s very popular traversal algorithm that is really worth knowing, its used in for both Tree and Graph data structures. The depth-first search goes deep in each branch before moving to explore another branch.

Here you could get familiar with

data structures.

#### Different types of implementation of DFS

There are three different orders for traversing a tree using DFS:

1. Inorder Traversal
2. Preorder Traversal
3. Postorder Traversal

##### Inorder Traversal

For inorder traversal, we traverse the left subtree first, then the root, then finally the right subtree.

Inorder → Left, Root, Right.

Inorder traversal for a BST means that we’re traversing the nodes in increasing order of their values.

There are two ways of implementing it, recursive and iterative.

Recursive:

public void inorderRecursive(Node root) {
if(root != null) {
dfsTraverseInorder(root.left);
visit(root.value)
dfsTraverseInorder(root.right);
}


Iterative:

To implement it iteratively we will need a Stack and following steps:

• Initialize a current node with root
• While current is not null or stack is not empty
• Keep pushing left child onto a stack, till we reach a current node’s left-most child
• Pop and visit the left-most node from stack
• Set current to the right child of the popped node
public void inorderIterative(Node root) {
Stack<Node> stack = new Stack<Node>();
Node current = root;

while(!stack.isEmpty() || current != null) {
while (current != null) {
stack.push(current);
current = current.left;
}

Node top = stack.pop();
visit(top.value);
current = top.right;
}
}


##### Preorder Traversal

For preorder traversal, we traverse the root first, then the left subtree, then finally the right subtree.

Preorder → Root, Left, Right.

To implement it iteratively we will need a Stack and following steps:

• Push root in our stack
• While stack is not empty
• Pop current node
• Visit current node
• Push right child, then left child to stack

Recursive:

public void traversePreorderRecursive(Node root) {
if(root != null) {
visit(root.value);
dfsTraversePreorder(root.left);
dfsTraversePreorder(root.right);
}
}


Iterative:

public void traversePreorderIterative(Node root) {
Stack<Node> stack = new Stack<Node>();
Node current = root;
stack.push(root);
while(!stack.isEmpty()) {
current = stack.pop();
visit(current.value);

if(current.right != null) {
stack.push(current.right);
}
if(current.left != null) {
stack.push(current.left);
}
}
}


#### Postorder Traversal

For postorder traversal, we traverse the left subtree first, then finally the right subtree, then finally the root.

Post order → Left, Right, Root.

To implement postorder traversal without recursion:

• Push root node in stack
• While stack is not empty
• Check if we already traversed left and right subtree
• If not then push right child and left child onto stack

Recursive:

public void traversePostorderRecursive(Node root) {
if (root != null) {
traversePostorderRecursive(root.left);
traversePostorderRecursive(root.right);
visit(root.value);
}
}


Iterative:

public void traversePostorderIterative() {
Stack<Node> stack = new Stack<Node>();
Node prev = root;
Node current = root;
stack.push(root);

while (!stack.isEmpty()) {
current = stack.peek();
boolean hasChild = (current.left != null || current.right != null);
boolean isPrevLastChild = (prev == current.right ||
(prev == current.left && current.right == null));

if (!hasChild || isPrevLastChild) {
current = stack.pop();
visit(current.value);
prev = current;
} else {
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
}
}


Tags:

Categories:

Updated: