Depth-First Search (DFS) for Trees
Depth-First Search (DFS) for Trees
Depth-First Search (DFS) is an algorithm used to traverse or search through tree or graph structures. It explores as far as possible along each branch before backtracking. DFS is useful for problems where you need to explore all possible paths or need to visit nodes in a specific order.
Overview
DFS starts from the root (or any arbitrary node in a graph) and explores as far as possible along each branch before backtracking. It can be implemented using recursion or a stack. DFS is useful for tasks such as searching paths, topological sorting, and solving puzzles.
Algorithm Steps
- Initialize: Start at the root node and mark it as visited.
- Explore: Recursively or iteratively visit all unvisited child nodes (or neighbors) of the current node.
- Backtrack: Once all nodes at the current branch have been explored, backtrack to explore other branches.
Example Implementation
Code Example:
//TreeNode
class TreeNode {
constructor(val) {
this.val = val; //Node value
this.left = null; // Left node
this.right = null; //Right node
}
}
DFS Pre Order (Root, Left, Right)
/**
* Perform DFS traversal on a tree using Preorder (Root, Left, Right).
* @param {TreeNode} root - The root of the tree.
* @return {number[]} - The values of the nodes in DFS order.
*/
const dfsPreorder = (root) => {
const result = [];
const traverse = (node) => {
if (!node) return;
result.push(node.val); // Process the node
traverse(node.left); // Visit left subtree
traverse(node.right); // Visit right subtree
};
traverse(root);
return result;
};
DFS In Order (Left, Root, Right)
/**
* Perform DFS traversal on a tree using Inorder (Left, Root, Right).
* @param {TreeNode} root - The root of the tree.
* @return {number[]} - The values of the nodes in DFS Inorder order.
*/
const dfsInorder = (root) => {
const result = [];
const traverse = (node) => {
if (!node) return;
traverse(node.left); // Visit left subtree
result.push(node.val); // Process the node
traverse(node.right); // Visit right subtree
};
traverse(root);
return result;
};
DFS Post Order (Left, Right, Root)
/**
* Perform DFS traversal on a tree using Postorder (Left, Right, Root).
* @param {TreeNode} root - The root of the tree.
* @return {number[]} - The values of the nodes in DFS Postorder order.
*/
const dfsPostorder = (root) => {
const result = [];
const traverse = (node) => {
if (!node) return;
traverse(node.left); // Visit left subtree
traverse(node.right); // Visit right subtree
result.push(node.val); // Process the node
};
traverse(root);
return result;
};
Output
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
/*
1
/ \
2 3
/ \ / \
4 5 6 7
*/
console.log(dfsPreorder(root)); // Output: [1, 2, 4, 5, 3, 6, 7]
console.log(dfsInorder(root)); // Output: [4, 2, 5, 1, 6, 3, 7]
console.log(dfsPostorder(root)); // Output: [4, 5, 2, 6, 7, 3, 1]
Iterative DFS Version
In-order
function inOrderTraversal(root) {
const stack = [];
const result = [];
while (root || stack.length) {
// Go as left as possible and push all left nodes to the stack
while (root) {
stack.push(root);
root = root.left;
}
// Backtrack by popping from the stack
root = stack.pop();
result.push(root.val); // Add the node value to the result
// Now, visit the right subtree
root = root.right;
}
return result;
}
Pre-order
function preOrderTraversal(root) {
const stack = [];
const result = [];
if (root) stack.push(root); // Start by pushing the root node to the stack
while (stack.length) {
root = stack.pop(); // Pop the top node from the stack
result.push(root.val); // Add the node value to the result
// Push right child first so left child is processed first
if (root.right) stack.push(root.right);
if (root.left) stack.push(root.left);
}
return result;
}
Post-order
function postOrderTraversal(root) {
const stack = [];
const result = [];
let lastVisited = null; // Track the last visited node
while (root || stack.length) {
if (root) {
// Go left as far as possible
stack.push(root);
root = root.left;
} else {
const peekNode = stack[stack.length - 1]; // Look at the top of the stack
// Check if we can visit the right subtree
if (peekNode.right && lastVisited !== peekNode.right) {
root = peekNode.right; // Go to the right subtree
} else {
// If right subtree is null or already visited, process current node
result.push(peekNode.val);
lastVisited = stack.pop(); // Mark this node as visited
}
}
}
return result;
}
Postorder 2
function dfsPostorder(root) {
if (!root) return [];
const stack = [root];
const result = [];
while (stack.length > 0) {
const node = stack.pop();
result.push(node.val);
// Push left first so right is processed first
if (node.left) stack.push(node.left);
if (node.right) stack.push(node.right);
}
return result.reverse(); // Reverse at the end to get Left -> Right -> Root order
}
DFS with Parent Tracking
function dfsWithParent(root) {
if (!root) return [];
const stack = [[root, null]]; // [node, parent]
const parentMap = new Map();
while (stack.length > 0) {
const [node, parent] = stack.pop();
parentMap.set(node, parent);
if (node.right) stack.push([node.right, node]);
if (node.left) stack.push([node.left, node]);
}
return parentMap;
}
DFS for Path Finding (Target Node)
function dfsFindPath(root, target) {
if (!root) return null;
const stack = [[root, [root.val]]]; // [node, pathSoFar]
while (stack.length > 0) {
const [node, path] = stack.pop();
if (node.val === target) return path;
if (node.right) stack.push([node.right, [...path, node.right.val]]);
if (node.left) stack.push([node.left, [...path, node.left.val]]);
}
return null;
}