Depth-First Search (DFS)

1. Depth-First Search (DFS) can be implemented in two main ways: recursively or iteratively using a stack.
2. Recursive Approach:
   • Create an array to store the results.
   • Write a helper recursive function that takes a node (object).
   • In this function, first add the value property of the current node to the results array.
   • Then, for each child node in the children array, recursively call the same function.
   • The initial call will be with the root object of the tree.
3. Iterative Approach (with a stack):
   • Create an array for the results and a stack for the nodes (objects) to visit.
   • Push the root node onto the stack.
   • While the stack is not empty:
     • Pop a node from the stack.
     • Add its value property to the results array.
     • Push all of its child nodes (from the children array) onto the stack. Important: To maintain the correct traversal order (left-to-right), you must push the children onto the stack in reverse order (right-to-left).
4. Don’t forget to handle the case where the input is null (an empty tree).

Solution 1: Recursive Approach

This approach is the most intuitive for tree-like structures because the structure of a tree is itself recursive.

Code with Comments:

const depthFirstSearch = (tree) => {
  // 1. Handle the edge case: if the tree is empty (null), return an empty array.
  if (!tree) {
    return [];
  }
 
  // 2. Create an array to store the traversal result.
  const result = [];
 
  // 3. Define a nested recursive function `traverse`.
  //    It will be called for each node (object) in the tree.
  function traverse(node) {
    // 4. Add the value of the current node to the result array.
    //    This is "visiting" the node.
    result.push(node.value);
 
    // 5. Iterate over all children of the current node.
    //    Ensure the node has children before iterating.
    if (node.children) {
      for (const child of node.children) {
        // 6. For each child node, recursively call the `traverse` function.
        //    This is the "deepening" part of the search.
        traverse(child);
      }
    }
  }
 
  // 7. Start the traversal by calling `traverse` on the root node of the tree.
  traverse(tree);
 
  // 8. Return the array with the traversal results.
  return result;
};

How It Works:

1. Base Case: The function first checks if the tree is null. If so, traversal is impossible, and it returns an empty array.
2. Initialization: An empty array result is created to collect the node values.
3. Recursive traverse function:
   • When called for a node, it immediately adds the node’s value (node.value) to the result array.
   • It then iterates through all children in the children array of that node.
   • For each child, it calls itself (traverse(child)). This is the key step in the recursion.
4. Start Traversal: The initial call traverse(tree) kicks off the recursive process from the root node.
5. Completion: When the very first call to traverse(tree) finishes its execution, the result array will contain all node values in the correct order.

Solution 2: Iterative Approach (with a Stack)

This approach uses a “Stack” data structure to keep track of the nodes to visit. It avoids deep recursion, which can lead to a stack overflow on very large or unbalanced trees.

Code with Comments:

const depthFirstSearch = (tree) => {
  // 1. Handle the edge case: if the tree is empty, return an empty array.
  if (!tree) {
    return [];
  }
 
  // 2. Create a array to store the result.
  const result = [];
  // 3. Create a stack and immediately push the root node (object) onto it.
  const stack = [tree];
 
  // 4. Start a loop that continues as long as there are nodes in the stack.
  while (stack.length > 0) {
    // 5. Pop the last node from the stack (LIFO - Last-In, First-Out).
    const node = stack.pop();
 
    // 6. "Visit" the node: add its value to the result array.
    result.push(node.value);
 
    // 7. Iterate over the children of the current node IN REVERSE ORDER.
    //    This is the key to the correct traversal order.
    if (node.children) {
      for (let i = node.children.length - 1; i >= 0; i--) {
        // 8. Push each child node onto the stack.
        stack.push(node.children[i]);
      }
    }
  }
 
  // 9. Return the array with the results.
  return result;
};

How It Works:

1. Initialization: It checks for null and creates a result array. A stack is also created, and the root tree object is immediately pushed onto it.
2. while Loop: The loop continues as long as the stack is not empty.
3. Pop Node: In each iteration, the top element is popped from the stack using stack.pop().
4. Visit Node: The value of the current node (node.value) is added to result.
5. Push Children to Stack: We iterate through the child nodes from right to left and push them onto the stack. This ensures that the left children are processed before the right ones, which corresponds to the classic DFS order.
6. Completion: When the while loop finishes, all nodes have been processed, and the function returns the result.