What is Depth First Search(DFS) in Tree Traversal?

What is Depth First Search in Tree Traversal?

Depth First Search (DFS) is a graph traversal algorithm that starts from a node (generally the root node in a graph or a tree) and then moves to the children nodes until the leaf nodes are reached.

There are many types of DFS algorithms in Tree Traversal:

• PreOrder Traversal
• InOrder Traversal
• PostOrder Traversal

PreOrder Traversal

PreOrder traversal is an algorithm where the root node is visited first, then the left child is visited, and then the right child is visited. Refer to the above picture (1 → 2 → 4 → 5 → 3).

InOrder Traversal

InOrder traversal is an algorithm where the left node is visited first, then the root node, and then the right node. Refer to the above picture (4 → 2 → 5 → 1 → 3).

PostOrder Traversal

PostOrder traversal is an algorithm where the left node is visited first, then the right node, and then the root node. Refer to the above picture (4 → 5 → 2 → 3 → 1).

public void preOrder(Node root){
    if(root == null){
        return;
    }
    System.out.print(root.data + " "); // You can perform any operation here, I am just printing it.
    preOrder(root.left);
    preOrder(root.right);
}

        

public void inOrder(Node root){
    if(root == null){
        return;
    }
    inOrder(root.left);
    System.out.print(root.data + " "); // You can perform any operation here, I am just printing it.
    inOrder(root.right);
}

        

public void postOrder(Node root){
    if(root == null){
        return;
    }
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.data + " "); // You can perform any operation here, I am just printing it.
}