Depth-First Search Traversal (Trees)

DFS Explained

Depth-First Search is a way traverse a node-based data structure, where each node can point to 2 or more nodes (ex. trees, graphs, tries, etc.).

In depth-first search (DFS), we explore nodes by going as deep as possible along a single branch before backtracking. We start at the source node and explore as far as we can before backtracking.

DFS is useful for tasks like topological sorting, finding connected components, and exploring paths. It’s often used when you’re interested in traversing deeply into a graph before backtracking.

In our example, we will look into implementing DFS in a tree structure. DFS can be implemented in three ways:

• Pre-Order
• In-Order
• Post-Order

Pre-Order Traversal

Pre-order Depth-First Search (DFS) is a tree traversal algorithm that explores nodes in a systematic manner, starting from the root and moving towards the leaves. It’s one of the three common types of DFS, alongside in-order and post-order traversal.

In pre-order DFS, the algorithm follows these steps:

1. Visit the Current Node: Start from the root node. Process or perform an operation on the current node.
2. Recursively Traverse Left Subtree: Move to the left child node and repeat the same process, visiting the left subtree in a recursive manner.
3. Recursively Traverse Right Subtree: After fully exploring the left subtree, move to the right child node and repeat the process, visiting the right subtree in a recursive manner.

By following this sequence, pre-order DFS explores the tree in a “root-left-right” order, meaning it visits the current node first, then its left subtree, and finally its right subtree. This traversal order is useful for tasks that require a hierarchical representation of the tree’s structure or when you need to process nodes in the order they appear in the tree.

Pre-order DFS is widely used for tasks like building expression trees, creating copies of trees, and evaluating mathematical expressions represented as trees. It offers insights into the tree’s structure while providing a flexible way to perform operations on each node in the tree.

Let’s look at the code for Pre-Order DFS traversal:

public static ArrayList<Integer> dfsPreOrder(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();
    return traverse(root, result);
}

public static ArrayList<Integer> traverse(TreeNode cur, ArrayList<Integer> result) {
    
    result.add(cur.data); // Add value to result

    if(cur.left != null) {
        traverse(cur.left, result);
    }
    if(cur.right != null) {
        traverse(cur.right, result);
    }
    return result;
}

We see here that we first initialize a result ArrayList where we will store our result. We then call our traverse() recursive function with that empty result list and the root.

We first place the root 9 into the result, and traverse down the left side.

• [ 9 ]

We get to 4, first add it to the result and traverse down the left side again.

• [ 9, 4 ]

We get to 1, and add it to the result. 1 does not have any children, so we return the result back up to 4.

• [ 9, 4, 1 ]

Now, we go down the right side. We get to 6, add it to the result, and see it has no children so we return it back to 4 as well.

• [ 9, 4, 1, 6 ]

Now, four returns the result up to 9, and we traverse down the right side of 9 the same way as we traversed down the left. We add the value, go left, adding each value to the result and then going right. We end up with

• [ 9, 4, 1, 6, 20, 15, 30 ] is the result.

In-Order Traversal

In-order Depth-First Search (DFS) is another tree traversal algorithm that explores nodes systematically, moving from the leftmost node to the rightmost node while respecting the hierarchical order of the tree.

Here’s how in-order DFS works:

1. Recursively Traverse Left Subtree: Start from the root node and move to its left child node. Continue this process recursively, exploring the left subtree in its entirety.
2. Visit the Current Node: After exploring the entire left subtree, visit the current node and perform any desired operation or processing.
3. Recursively Traverse Right Subtree: Finally, move to the right child node of the current node and recursively explore the right subtree.

In in-order DFS, the traversal follows a “left-root-right” pattern, ensuring that nodes are visited in ascending order of their values (assuming you’re dealing with a binary search tree). This ordering is particularly useful for tasks like producing a sorted list of elements from a binary search tree or performing operations that require elements to be processed in their sorted order.

In summary, in-order DFS explores the tree by first traversing the left subtree, then visiting the current node, and finally exploring the right subtree. It’s valuable for tasks that involve ordered processing or require elements to be accessed in a specific sequence.

Let’s look at the code for In-Order DFS traversal:

public static ArrayList<Integer> dfsInOrder(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();
    return traverse(root, result);
}

public static ArrayList<Integer> traverse(TreeNode cur, ArrayList<Integer> result) {
    if(cur.left != null) {
        traverse(cur.left, result);
    }

    result.add(cur.data); // Add value to result

    if(cur.right != null) {
        traverse(cur.right, result);
    }
    return result;
}

Similarly to before, we first initialize a result ArrayList where we will store our result. We then call our traverse() recursive function with that empty result list and the root.

When we traverse(), we first go all the way down the left side until we reach 1. We then add it to the result, since it has no left child. Since it has no right child either, we return it to 4.

• [ 1 ]

Now we are at 4. We first add the 4 to the result before traversing down the right side of 4.

• [ 1, 4 ]

We end up at the right side of 4, at value 6. It has no left child, so we add it to the result. It has no right child either, so we return the result back to 4.

• [ 1, 4, 6 ]

We have traversed both of 4’s children, so we return that back to 9. We have finished traversing the left side of 9, so we add 9 to the result and traverse down the right side of 9.

• [ 1, 4, 6, 9 ]

Similarly to before, we will traverse down the left side of 9’s right branch and continue to follow that left-root-right pattern until we are left with the final result

• [ 1, 4, 6, 9, 15, 20 , 30 ] is the result.

Post-Order Traversal

Lastly, Post-order Depth-First Search (DFS) is our final tree traversal algorithm that explores nodes systematically, starting from the leaves and moving towards the root.

Here’s how post-order DFS works:

1. Recursively Traverse Left Subtree: Start from the root node and move to its left child node. Continue this process recursively, exploring the left subtree in its entirety.
2. Recursively Traverse Right Subtree: After fully exploring the left subtree, move to the right child node of the current node and recursively explore the right subtree.
3. Visit the Current Node: Once both the left and right subtrees have been explored, visit the current node and perform any desired operation or processing.

In post-order DFS, the traversal follows a “left-right-root” pattern. It explores the tree’s nodes from the bottom up, first visiting the leaves before moving towards the root. This order can be useful for tasks that require post-processing, such as deleting nodes from a tree while ensuring that child nodes are deleted before their parents.

Post-order DFS is often used for tasks like freeing memory allocated for a tree’s nodes, evaluating mathematical expressions represented as trees, and other operations that require a bottom-up approach.

In summary, post-order DFS explores the tree by first traversing both subtrees, then visiting the current node. It’s beneficial for tasks that involve processing or dealing with nodes in a bottom-up manner.

Let’s look at the code for Post-Order DFS traversal:

public static ArrayList<Integer> dfsPostOrder(TreeNode root) {
    ArrayList<Integer> result = new ArrayList<>();
    return traverse(root, result);
}

public static ArrayList<Integer> traverse(TreeNode cur, ArrayList<Integer> result) {
    if(cur.left != null) {
        traverse(cur.left, result);
    }

    if(cur.right != null) {
        traverse(cur.right, result);
    }

    result.add(cur.data); // Add value to result

    return result;
}

Again, we first initialize a result ArrayList where we will store our result. We then call our traverse() recursive function with that empty result list and the root.

We traverse all the way down the left side of the tree until we reach 1. It has no left or right children, so we add it to the result and return it back up to 4.

• [ 1 ]

Then we traverse down the right side of 4 and find 6. We add it to the result and similarly, return it back to 4.

• [ 1, 6 ]

We are now at 4 and we have traversed both its left and right branches. We add it to the result and return it to 9.

• [ 1, 6, 4 ]

Now we are at 9. We traverse down the right path to 20, and see that it has a left child 15. We go to 15 and see it has no children so we add it to the result and return it back to 20.

• [ 1, 6, 4, 15 ]

At 20, we see we have a right child, 30 so we traverse there. It has no children, so we add it to the result and return it to 20.

• [ 1, 6, 4, 15, 30 ]

Now, we have traversed both branches of 20, so we add it to the result and return it to 9.

• [ 1, 6, 4, 15, 30, 20 ]

We have also explored both branches (left & right) of 9, so we add 9 to the final result.

• [ 1, 6, 4, 15, 30, 20, 9 ] is the result.

We have explored the three types of depth-first-search tree traversal. I hope this helps!