Search code examples
javascriptalgorithmdomgraph-algorithm

why is DOM tree oder preorder, depth-first traversal?

why is DOM tree oder preorder, depth-first traversal?

What are the advantages of this design choice compared to other traversal like BFT?

I was just looking into DOM standard and found the definition of preceding and following :

An object A is preceding an object B if A and B are in the same tree and A comes before B in tree order.

An object A is following an object B if A and B are in the same tree and A comes after B in tree order.

Just like most programming paradigms the Web platform has finite hierarchical tree structures, simply named trees. The tree order is preorder, depth-first traversal.

Solution

  • Depth-first traversal is generally the easiest traversal style, since you can do it recursively or with an explicit stack; breadth-first requires a queue which is, in some sense, a more complicated data-structure. But I think there is a simpler answer than tradition or simplicity: depth-search traversal of an (X)HTML tree results in the text nodes being traversed in presentation order.

    Consider this relatively simple HTML subtree.

    Or, in HTML:

    <p>Consider this <em>relatively</em> simple <a href="http://en.wikipedia.org/wiki/HTML">HTML</a> subtree</p>

    As a tree (leaving out whitespace and attributes):

                            <P>
                         |
      +----------+-------+-----+------+               
______|______  __|__  ___|__  _|_  ___|___
Consider this   <EM>  simple  <A>  subtree
                 |             |
             ____|_____      __|__
             relatively       HTML

    Depth-first traverse:

    <P>, Consider this, <EM>, relatively, simple, <A>, HTML, subtree

    Breadth-first traverse:

    <P>, Consider this, <EM>, simple, <A>, subtree, relatively, HTML