基于JavaScript的深度优先遍历结果与定义不符问题咨询

Hey there! Let's break down why you're seeing a discrepancy between the depth-first traversal (DFS) output from that JavaScript tree article and what you expect based on Wikipedia's diagram.

First, a key point: DFS isn't a single fixed traversal order #

DFS is an umbrella term for a family of traversal strategies that all follow the "explore as far as possible along a branch before backtracking" rule. But it has three widely used variants, and this is where confusion often pops up:

• Pre-order traversal: Visit the current node first, then recursively traverse the left subtree, followed by the right subtree. (Root → Left → Right)
• In-order traversal: Recursively traverse the left subtree first, visit the current node, then traverse the right subtree. (Left → Root → Right) — this is the one that returns sorted values for binary search trees.
• Post-order traversal: Recursively traverse the left subtree, then the right subtree, and finally visit the current node. (Left → Right → Root)

The most likely reason for your mismatch: Different DFS variants in play #

It’s almost certain that the article’s code implements one of these variants, while the Wikipedia diagram illustrates another. For example:

• If the article’s DFS method looks like this (a common pre-order implementation):

  depthFirstTraversal() {
    const result = [];
    const traverse = (node) => {
      result.push(node.value); // Visit node first
      if (node.left) traverse(node.left);
      if (node.right) traverse(node.right);
    };
    traverse(this.root);
    return result;
  }
  

  Its output will follow the pre-order sequence. If Wikipedia’s diagram shows in-order or post-order traversal, the results will naturally differ.

To confirm, map the traversal steps manually #

Grab the exact tree structure from the article and walk through both:

1. For the article’s code: Trace the recursive calls to see exactly when each node gets added to the result array.
2. For Wikipedia’s diagram: Follow the path shown, noting whether it visits a node before diving into its children, between left and right children, or after both children are processed.

If you can share the specific code snippet from the article and your expected/actual output, we can pinpoint the exact variant mismatch—but this variant confusion is by far the most common cause of this kind of discrepancy.

内容的提问来源于stack exchange，提问作者theamateurdataanalyst