Depth First

A DepthFirst traversal of this tree:

        A
     B     C
    D E   F G

visits the nodes in this order: A B D E C F G

See BreadthFirst for another common way to traverse trees.

---

Depth first traversals are easy to write in recursive languages because the stack of untaken branches can be implicitly held in the runtime stack. But fear the day you meet a "tree" with a cycle (loop) in it! In PerlLanguage, "defined caller(50)" offers some advance warning of this.

  void visit() {
    left.visit();
    right.visit();
  }

Useful work can be done before, between or after the recursive calls yielding preorder (PolishNotation), inorder (InfixNotation), and endorder (PostfixNotation) traversals. The recursion is broken by making empty trees be NullObjects that implement visit() but do nothing.

---

CategoryJargon