Depth First Search in Java

Depth First Search [DFS]

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

Note: This post focuses on DFS as applied to tree traversal. DFS is equally applicable to graphs, where it is used for cycle detection, topological sorting, finding connected components, and more. The core idea remains the same – explore as deep as possible before backtracking – but graph DFS requires tracking visited nodes to avoid infinite loops in cyclic structures.

Here you can get familiar with

• Trees
• Graphs

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

Tree Depth First Search

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.

Time complexity: O(n), where n is the number of nodes. Space complexity: O(h), where h is the height of the tree (O(log n) for balanced trees, O(n) for skewed trees).

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

Recursive:

public void inorderRecursive(Node root) {
    if(root != null) {
        inorderRecursive(root.left);
        visit(root.value);
        inorderRecursive(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.

Time complexity: O(n), where n is the number of nodes. Space complexity: O(h), where h is the height of the tree.

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);
        traversePreorderRecursive(root.left);
        traversePreorderRecursive(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 the right subtree, and finally the root.

Post order → Left, Right, Root.

Time complexity: O(n), where n is the number of nodes. Space complexity: O(h), where h is the height of the tree.

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(Node root) {
    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);
            }
        }
    }
}

DFS vs BFS

DFS and Breadth-First Search (BFS) are the two fundamental approaches to tree and graph traversal. DFS dives deep into one branch before exploring siblings, while BFS explores all nodes at the current depth level before moving deeper. In terms of complexity, both run in O(n) time for trees, but their space usage differs: DFS uses O(h) space (the height of the tree), while BFS uses O(w) space (the maximum width of the tree). For a balanced binary tree, the width can be up to n/2 at the deepest level, making BFS more memory-intensive. DFS is generally preferred when searching deep structures or when the solution is likely far from the root. BFS is the natural choice when looking for the shortest path or when the target is expected to be close to the root.