Non-recursive Preorder Traversal

Published on 1st of November 2008. Copyright Tavs Dokkedahl. Displayed 2785 time(s)

When I was writing the script for in-page search a la Apple Safari I had to find all text nodes in a document and at the same time order them as they are created in the document.

As the DOM stores the elements of a HTML document as a tree datastructure you can obtain such an ordering by doing a preorder traversal of the tree.

• Part 1 - A brief introduction to trees
• Part 2 - Recursive preorder
• Part 3 - Non-recursive preorder
• Part 4 - Different kind of traversals