Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 723
P K Avatar asked Apr 19 '13 18:04

P K


2 Answers

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 raw form:

<p>Consider this <emph>relatively</emph> simple <a href="...">HTML</a> subtree</p>

As a tree (leaving out whitespace and attributes):

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

Depth-first traverse:

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

Breadth-first traverse:

<P>, Consider this, <EMPH>, simple, <A>, subtree, relatively, HTML
like image 124
rici Avatar answered Nov 09 '22 08:11

rici


A depth-first search requires memory on the order of the tree's height, but a breadth-first search requires memory on the order of the cardinality of the tree's vertices. In other words, breadth-first search is a memory hog compared to depth-first search.

like image 21
Zim-Zam O'Pootertoot Avatar answered Nov 09 '22 09:11

Zim-Zam O'Pootertoot