Walk DOM Tree in Reverse?

[delraydog]

It's quite simple to walk to the DOM tree going forward however I can't
figure out a nice clean way to walk the DOM tree in reverse. Checking
previousSibling is not sufficient as the previousSibling could be a
node which has childNodes and therefore the 'true' previousSibling
would be the *deepest* lastChild of the previousSibling...

For example, given this graph:

1 myAnchor nodeType 1
2 myAnchorText1 nodeType 3
3 myAnchorText2 nodeType 3
4 myBold nodeType 1
5 myText1 nodeType 3
6 myText2 nodeType 3

I want to be able to walk the tree in reverse starting from position 6
so that I get:

myText2
myText1
myBold
myAnchorText2
myAnchorText1
myAnchor

Any ideas?

Thanks,
Cliff.

 

[VK]

It's quite simple to walk to the DOM tree going forward however I can't
figure out a nice clean way to walk the DOM tree in reverse. Checking
previousSibling is not sufficient as the previousSibling could be a
node which has childNodes and therefore the 'true' previousSibling
would be the *deepest* lastChild of the previousSibling...

For example, given this graph:

1 myAnchor nodeType 1
2 myAnchorText1 nodeType 3
3 myAnchorText2 nodeType 3
4 myBold nodeType 1
5 myText1 nodeType 3
6 myText2 nodeType 3

I want to be able to walk the tree in reverse starting from position 6
so that I get:

myText2
myText1
myBold
myAnchorText2
myAnchorText1
myAnchor

Any ideas?

I might be missing your problem:- an actual HTML code would be helpful.
The tree is...uhm... a tree. It means that can be a lot of children
(leaves) but only one parent (branch) for each child. Or - using
database terms - these are one-to-many relations, not many-to-many.

 

[Thomas 'PointedEars' Lahn]

It's quite simple to walk to the DOM tree going forward however I can't
figure out a nice clean way to walk the DOM tree in reverse. Checking
previousSibling is not sufficient as the previousSibling could be a
node which has childNodes and therefore the 'true' previousSibling
would be the *deepest* lastChild of the previousSibling...

You have to recurse into the subtree of the previousSibling until
there are no more child nodes, i.e. until there is no lastChild.

For example, given this graph:

1 myAnchor nodeType 1
2 myAnchorText1 nodeType 3
3 myAnchorText2 nodeType 3
4 myBold nodeType 1
5 myText1 nodeType 3
6 myText2 nodeType 3

I want to be able to walk the tree in reverse starting from position 6
so that I get:

myText2
myText1
myBold
myAnchorText2
myAnchorText1
myAnchor

Any ideas?

myText2.previousSibling....parentNode.previousSibling.lastChild...
..previousSibling....parentNode...

See?


PointedEars

 

[Lasse Reichstein Nielsen]

It's quite simple to walk to the DOM tree going forward however I can't
figure out a nice clean way to walk the DOM tree in reverse.

You want a depth-first right-to-left traversal of the nodes.
That sounds like a job for recursion:

---
function traverseDFRTL(element, action) {
for(var child = element.lastChild; child; child = child.previousSibling) {
traverseDFRTL(child, action);
}
action(element);
}
---

Calling
---
traverseDFRTL(someElement, function(node) {
alert([node.tagName, node.nodeType]);
});
---
will alert the nodes in the desired order.


If you don't want recursion, you can do it iteratively as well, but it
will never be as simple.

/L

 

[Thomas 'PointedEars' Lahn]

---
function traverseDFRTL(element, action) {
for(var child = element.lastChild; child; child =
child.previousSibling) {
traverseDFRTL(child, action);
}
action(element);
}

Very nice. There is one catch, though: after the very first node of the
document tree has been processed, action() is called with `null', and if
the reference to the above function is passed as callback, there will be
a script error in the end ("null has no properties"). So either the
callback is modified so that `node.tagName' and `node.nodeType' are only
evaluated if `node' refers to an object, or the second call of `action'
should not take place if `element' does not refer to an object.
Furthermore, text nodes have no `tagName' property.

It would also be nice if one could use the return value of traverseDFTRL(),
and to allow for another identifier without modifying the function body.

Hence the following suggestion:

function isMethod(a)
{
var t;
return (a && ((t = typeof a) == "function" || t == "object"));
}

function traverseDFRTL(element, action)
{
for (var child = (element || document.documentElement).lastChild;
child;
child = child.previousSibling)
{
arguments.callee(child, action);
}

if (isMethod(action))
{
return action(element);
}
}

var nodes = [];

alert(traverseDFRTL(
null,
function(node)
{
if (node)
{
nodes.push(node.nodeName
+ (typeof node.nodeValue == "string"
? (' "' + node.nodeValue + '"')
: ""));
}

return nodes;
}).join("\n"));


PointedEars

 

[Lasse Reichstein Nielsen]

Very nice. There is one catch, though: after the very first node of the
document tree has been processed, action() is called with `null',

I can't see how. The "action" callback function is only ever called
with the value of the "element" parameter. It can only be called with
a null value if "element" is null. The recursive calls are only made
if "child" is not null, so they can't cause it, so "action" should
only be called with null arguemnt if someone calls traverseDFRTL with
a first parameter that is null.

and if the reference to the above function is passed as callback,
there will be a script error in the end ("null has no properties").

Could you post an example, including which browser causes it?

Furthermore, text nodes have no `tagName' property.

True. It was just a quick example.

It would also be nice if one could use the return value of traverseDFTRL(),

What would the return value be? But yes, it could easily be turned into
a catemorphism (fold-like function):

function foldDOM(element, action) {
var childRets = [];
for(var child = element.lastChild; child; child = child.previousSibling) {
childRets.push(foldDOM(child, action));
}
return action(element, childRets);
}

Then you could collect the innerText of a DOM element as:

foldDOM(element, function(node,childTexts) {
if (node.nodeType == 3) { // Text node
return node.nodeValue;
} else { // Element node
return childTexts.join("");
}
});

and to allow for another identifier without modifying the function body.

If you want another name for it, treat the above as a function expression,
not a function declaration. Then you can call it whatever you like:

var myOwnName = function foldDOM(...){...foldDOM(...)...};

I don't find the use of arguments.callee particularly readable.
If a function can't know its own declared name inside its body,
what can it know?

Hence the following suggestion:

function isMethod(a)
{
var t;
return (a && ((t = typeof a) == "function" || t == "object"));
}

function traverseDFRTL(element, action)
{
for (var child = (element || document.documentElement).lastChild;
child;
child = child.previousSibling)
{
arguments.callee(child, action);
}

if (isMethod(action))
{
return action(element);

If you insist on having a default argument, it should also apply here,
so,
return action(element || document.documentElement);
For default parameters, I prefer setting them at the top of the function,
i.e., as first line:
element = element || document.documentElement;

}

if you make this test (and I wouldn't - someone callig the function
should know that he is expected to pass a function as second argument),
I would at least fail if it's not:
else {
throw Error("Not a function as second argument!");
}

function(node)
{
if (node)

So here you depend on having the documentElement being traversed, but
null still being passed to the action function. That seems awfully
fragile and not very generic. I prefer to have a more generic, and
preferably simpler, function like my original traversal or the foldDOM
above, and then create a specialized function to call it with special
arguments that makes sense to the page it is used on.

/L

 

[Csaba Gabor]

It's quite simple to walk to the DOM tree going forward however I can't
figure out a nice clean way to walk the DOM tree in reverse.

You want a depth-first right-to-left traversal of the nodes.
That sounds like a job for recursion:

---
function traverseDFRTL(element, action) {
for(var child = element.lastChild; child; child = child.previousSibling) {
traverseDFRTL(child, action);
}
action(element);
}
---

Calling
---
traverseDFRTL(someElement, function(node) {
alert([node.tagName, node.nodeType]);
});
---
will alert the nodes in the desired order.


If you don't want recursion, you can do it iteratively as well, but it
will never be as simple.

<body onload="test()"><table><tr><td>Help</td></tr></table>
<script type='text/javascript'>

function lessSimpleTraverseDFRTL(element, action) {
var next, prev=element.lastChild || element, lcOK=true;
for (; prev!=element; lcOK=prev.parentNode!=(prev=next)) {
if (lcOK && (next=prev.lastChild)) continue; else action (prev);
next = prev.previousSibling || prev.parentNode; }
action(element); }

function test() {
lessSimpleTraverseDFRTL(document.body, function(node) {
alert(node.nodeName+ "\n" + outerHTML(node)); }); }

function outerHTML(elem) {
if (elem.outerHTML) return elem.outerHTML;
var dup=elem.cloneNode(true); //event handlers, some attribs omitted
var dummyDiv=elem.ownerDocument.createElement('DIV');
dummyDiv.appendChild(dup);
var outer=dummyDiv.innerHTML;
delete dummyDiv;
return outer;
}
</script>
<div><span>Hi mom</span><p>Hi dad</p></div>
</body>


Tested with IE 6, FF 1.5.0.1,
Csaba Gabor from Vienna

 

[Csaba Gabor]

It's quite simple to walk to the DOM tree going forward however I can't
figure out a nice clean way to walk the DOM tree in reverse.

You want a depth-first right-to-left traversal of the nodes.
That sounds like a job for recursion:

---
function traverseDFRTL(element, action) {
for(var child = element.lastChild; child; child = child.previousSibling) {
traverseDFRTL(child, action);
}
action(element);
}
---

Calling
---
traverseDFRTL(someElement, function(node) {
alert([node.tagName, node.nodeType]);
});
---
will alert the nodes in the desired order.


If you don't want recursion, you can do it iteratively as well, but it
will never be as simple.

<body onload="test()"><table><tr><td>Help</td></tr></table>
<script type='text/javascript'>

function lessSimpleTraverseDFRTL(element, action) {
var next, prev=element.lastChild || element, lcOK=true;
for (; prev!=element; lcOK=prev.parentNode!=(prev=next)) {
if (lcOK && (next=prev.lastChild)) continue; else action (prev);
next = prev.previousSibling || prev.parentNode; }
action(element); }

Kidding aside, the iterative version does offer something that the
recursive version doesn't because the recursive version only does
subtrees. The iterative version is happy to walk all the way back to
the root, from a given element. I found it quite instructive.

<body onload="test()"><table><tr><td id=td>Help</td></tr></table>
<script type='text/javascript'>

function backwalk(elem, action) {
// iterative reverse depth first traversal to root from elem
for (var next, lcOK=false; elem; lcOK=elem.parentNode!=(elem=next)) {
if (lcOK && (next=elem.lastChild)) continue; else action (elem);
next = elem.previousSibling || elem.parentNode; } }

function test() {
backwalk(document.getElementById('td'), function(node) {
alert(node.nodeName+ " (" + node.nodeType +
")\n" + outerHTML(node)); }); }

function outerHTML(elem) {
if (elem.outerHTML||elem.nodeType>8) return elem.outerHTML;
var dup=elem.cloneNode(true);
var dummyDiv=elem.ownerDocument.createElement('DIV');
dummyDiv.appendChild(dup);
var outer=dummyDiv.innerHTML;
delete dummyDiv;
return outer; }

</script>
<div><span>Hi mom</span><p id=p>Hi dad</p></div>
</body>


Plus the code is simpler.
Csaba Gabor from Vienna

 

[Thomas 'PointedEars' Lahn]

I can't see how. The "action" callback function is only ever called
with the value of the "element" parameter. It can only be called with
a null value if "element" is null. The recursive calls are only made
if "child" is not null, so they can't cause it, so "action" should
only be called with null arguemnt if someone calls traverseDFRTL with
a first parameter that is null.

You are correct, the original code runs without error. It was in fact my
optimization which caused the problem. I passed `null' for triggering the
default value `document.documentElement' and forgot that this would not
affect the value of `element' as passed to the second action() call.

It would also be nice [...] to allow for another identifier without
modifying the function body.

If you want another name for it, treat the above as a function expression,
not a function declaration. Then you can call it whatever you like:

var myOwnName = function foldDOM(...){...foldDOM(...)...};

I don't find the use of arguments.callee particularly readable.
If a function can't know its own declared name inside its body,
what can it know?

Think about it. That there are function expressions, i.e. functions
are first-level objects, is precisely why arguments.callee is useful.

If you insist on having a default argument, it should also apply here,
so,
return action(element || document.documentElement);

In fact, it MUST then, unless one sets a requirement for checking
the argument of the callback in the callback. See above.

For default parameters, I prefer setting them at the top of the function,
i.e., as first line:
element = element || document.documentElement;

I prefer

if (!element) element = document.documentElement;

as it strikes me as being more efficient.

if you make this test (and I wouldn't - someone callig the function
should know that he is expected to pass a function as second argument),
I would at least fail if it's not:
else {
throw Error("Not a function as second argument!");
}

Agreed, although I would consider an alternative to a plain `throw'.


PointedEars

 

[Lasse Reichstein Nielsen]

function backwalk(elem, action) {
// iterative reverse depth first traversal to root from elem
for (var next, lcOK=false; elem; lcOK=elem.parentNode!=(elem=next)) {
if (lcOK && (next=elem.lastChild)) continue; else action (elem);
next = elem.previousSibling || elem.parentNode; } }

I'm not entirely sure I read this correctly, but doesn't it follow
just a path through prevous siblings and parents from a note to the
root? It doesn't traverse children of the siblings, nor later
siblings at the same level.

An iterative function that works like the original traversal could be:
---
function leftMostInnerMostDescendent(node) {
while (node.hasChildNodes()) {
node = node.lastChild;
}
return node;
}

function traverse(element, action) {
var next = leftMostInnerMostDescendent(element);
do {
action(next);
if (next.previousSibling) {
next = leftMostInnerMostDescendent(next.previousSibling);
} else {
next = next.parentNode;
}
} while (next != element);
action(element);
}
---

A much more engenious (but probably dangerous) method is to use
rotation of the tree, putting the parent as the last child of its
first child and continuing that until the original shape is
restored (as it will be eventually). It's probably not doable in
general in a tree structure like HTML where not every node can
be a child of every other node.

/L

 

[Lasse Reichstein Nielsen]

Think about it. That there are function expressions, i.e. functions
are first-level objects, is precisely why arguments.callee is useful

It is useful for creating recursion on anonymous functions, but since
we also have named function expressions, with the scope of the name
being only the body of the function, that can be used for recursion
as well (and for pretty much nothing else).

The advantage I can see for arguments.callee is that Javascript
code is often canibalized and snippets put into other scripts.
Using a named function for recursion means that whoever copies
the the function and renames it must be aware that it is recursive.

On the other hand, using the name to call recursively is much more
readable (at least to me), and I don't have any scruples making code
that needs to be understood before it's copied

/L

 

[Thomas 'PointedEars' Lahn]

It is useful for creating recursion on anonymous functions, but since
we also have named function expressions, with the scope of the name
being only the body of the function, that can be used for recursion
as well (and for pretty much nothing else).

The advantage I can see for arguments.callee is that Javascript
code is often canibalized and snippets put into other scripts.

Exactly. Think about assigning the Function object reference to a
property of another object. With `arguments.callee', you can use
the function in that context without having to change its code.


PointedEars

 

[Csaba Gabor]

I'm not entirely sure I read this correctly, but doesn't it follow
just a path through prevous siblings and parents from a note to the
root? It doesn't traverse children of the siblings, nor later
siblings at the same level.

your traverse is doing what my lessSimpleTraverseDFRTL is doing two
posts above. Looking at backwalk, which is essentially the same:
The basic idea is that, when we can, we go to the last child and don't
do any action. That's the 'if' (I'll get to the lcOK in a moment). If
we can't go to the last child, that means we must go to the previous
sibling, and failing that, to the parentNode. That's what the 'next='
is about. But before we do that, we take the action, which is what the
'else' is about.

So this little, "go to the lastChild, otherwise the previousSibling,
otherwise the parentSibling" has one failing. If you go to the
parentNode from a child, you'll wind up right back at the lastChild.
Therefore, better prevent going to the lastChild if the parent of the
old element is the same as the new element. And that is what the
'lcOK' (OK to go to lastChild) is doing. I set it to false at the
outset, because if we start backwards from a given elem, we don't want
to look at the starting elem's children. If you start my example from
document.getElementById('p'), it will include the TD of the table.

An iterative function that works like the original traversal could be: ....
function traverse(element, action) {
var next = leftMostInnerMostDescendent(element);

I think of .lastChild as a rightmost child

....

A much more engenious (but probably dangerous) method is to use
rotation of the tree, putting the parent as the last child of its
first child and continuing that until the original shape is
restored (as it will be eventually). It's probably not doable in
general in a tree structure like HTML where not every node can
be a child of every other node.

I never saw this before - it's interesting, reminding me of splay trees
- would you be a little more specific, please. By putting the parent
as the last child of its first child, do you also mean that the parent
should disconnect that first child as its child? And where does the
action come in? If you would give the recursive form of the function,
at least in some pseudo code, that would be great.

Csaba

 

[Lasse Reichstein Nielsen]

Lasse Reichstein Nielsen wrote:

your traverse is doing what my lessSimpleTraverseDFRTL is doing two
posts above.

I guess the "continue" threw me off
I *think* I understand it now

I think of .lastChild as a rightmost child

*cough*right*cough*

[traversal by pointer reversal]

I never saw this before - it's interesting, reminding me of splay trees
- would you be a little more specific, please.

I *wish* I could find a reference for this on the web (or in any of my
books). It was just something my advisor mentioned to me at some point,
as a well known method for traversing trees.


Assume that we have some node structure with the operations of DOM
nodes, but without the HTML structure requirements. Then the following
algorithm will traverse all nodes (sadly not necessarily visiting each
just once):


function traverseByPointerReversal(node, action) {
// A sentinel node for knowing when to end.
var root = new Node("fakeroot"); // or something.
root.appendChild(node);

node = root;
do { // invariant: node is the root of a tree containing all the nodes.
// node always has at least one child
var child = node.firstChild;
node.removeChild(child);
child.appendChild(node);
node = child;
if (node != root) { action(node); }
} while (node != root);
}


// example code, with "mockup" nodes to show the transformations:
function Node(name) {
this.name = name;
this.children = [];
}
Node.prototype.appendChild = function(childNode) {
this.children.push(childNode);
if (this.children.length == 1) {
this.firstChild = childNode;
}
};
Node.prototype.removeChild = function(childNode) {
this.children.shift(); // for this algorithm, only first child is removed
this.firstChild = this.children[0];
}
Node.prototype.toString = function() { // show tree structure
var cs = [];
for (var i = 0; i < this.children.length; i++) {
cs = this.children.toString();
}
return this.name + ((cs.length > 0) ? ":[" + cs + "]" : "");
};
// example tree:
// A
// / | \
// B C D
// / \
// E F
var A = new Node("A");
var B = new Node("B");
var C = new Node("C");
var D = new Node("D");
var E = new Node("E");
var F = new Node("F");
A.appendChild(B);
A.appendChild(C);
A.appendChild(D);
D.appendChild(E);
D.appendChild(F);
alert(A); // A:[B,C,D:[E,F]]

traverseByPointerReversal(A, function(node){alert(node);});

This shows how the tree looks at each step, since the node in question
is always the root at the time it is "action"'ed.

By putting the parent as the last child of its first child, do you
also mean that the parent should disconnect that first child as its
child?

It should, yes.

And where does the action come in?

That is a problem, since some nodes are traversed more than once,
and the algorithm doesn't store information about where it came
from or what nodes are really pointer-reversed parent nodes.
So for the purpose of the OP, it's not very usable. I do think it's
a neat algorithm, though

If you would give the recursive form of the function, at least in
some pseudo code, that would be great.

The point is to not be recursive, and not use extra space for a stack.
I believe (without knowing for sure) that a similar method is used by
garbage collectors to traverse a tree without using more than constant
extra space.

/L

 

[Lasse Reichstein Nielsen]

Lasse Reichstein Nielsen wrote:

Exactly. Think about assigning the Function object reference to a
property of another object. With `arguments.callee', you can use
the function in that context without having to change its code.

I won't have to change any code if I used the named function
expression either. The scope of the function name is only the function
body, so nobody else should be using it anyway (yes, I know some
browsers fails to comply with ECMAScript on this).


var deadloop = function omega() { omega(); }
var someObject = {};
someObject.liveloop = deadloop;
someObject.liveloop(); // loops just as dead!


If I had to make a function that was portable and where the user
could change its name, I would use a wrapper function:

function traverse(node, action) {
function traverseRec(node) {
// ... traverseRec(child); .... action(node) ...
}
traverseRec(node || documentElement, action);
}

It also provides a suitable point for adding default parameters
without having to do it on each recursive call where we know it's not
necessary, and it avoids passing constant parameters on every call.
All in all a win-win-win situation

/L

 

[Thomas 'PointedEars' Lahn]

I won't have to change any code if I used the named function
expression either.

If you call the method as a method of the Variable Object, it
will work different as if called as method of another object.

And without using arguments.callee, you will have to have a
named reference to it always.


PointedEars

 

[Lasse Reichstein Nielsen]

If you call the method as a method of the Variable Object, it
will work different as if called as method of another object.

That is correct, but only it uses the "this" operator for anything.

A recursive function that calls itself by name will do so without
an object reference, so the "this" operator will refer to the global
object. Unless you actually need access to a global variable that
is shadowed by nested declaration, you don't need this reference
to the global object, so the function will probably not use it.

Calling the function recursively through arguments.callee will
have the called function's "this" operator refere to the calling
function's arguments object. While interesting, messing with
the caller's activation record is not good style for a recursive
function

All in all, a recursive function should not use the "this" operator,
and then there is no difference how it is called.

And without using arguments.callee, you will have to have a
named reference to it always.

Inside a named function expression, you have just that.

/L

 

[Thomas 'PointedEars' Lahn]

[...]
All in all, a recursive function should not use the "this" operator,

Utter nonsense.

[...]

And without using arguments.callee, you will have to have a
named reference to it always.

Inside a named function expression, you have just that.

Exactly. You missed the point.


PointedEars

 

[Lasse Reichstein Nielsen]

[...]
All in all, a recursive function should not use the "this" operator,

Utter nonsense.

You are entitled to your, unsupported, opinion.

A function using the "this" operator is meant to be used as a method,
operating on the object it is on.

A recursive function (i.e., a function defined in terms of itself) is
a computational device unrelated to object oriented programming.

While a method can call itself as a function (and not just as a method
on the same object), and a function can use the "this" operator in a
"novel" way that is different from its normal meaning, it is a
confusion of styles that I recommend against. It is more important
to be readable and use idioms the way the reader expects, than to
be able to reduce the code by a line and a few cycles of execution
time.

[...]

And without using arguments.callee, you will have to have a
named reference to it always.

Inside a named function expression, you have just that.

Exactly. You missed the point.

Apparently. I still can't find it.

/L

 

[Thomas 'PointedEars' Lahn]

[...]
All in all, a recursive function should not use the "this" operator,

Utter nonsense.

You are entitled to your, unsupported, opinion.

Yes, I am.

A function using the "this" operator is meant to be used as a method,
operating on the object it is on.
True.

A recursive function (i.e., a function defined in terms of itself) is
a computational device unrelated to object oriented programming.

That is shortsighted thinking at best. Why should a recursive method not
be allowed in object-oriented programming? If a feature can be implemented
with a recursive call, you would dare force a developer to use the
iterative approach, or write less easier maintainable code instead? Just
because it does not fit your argumentation, I presume. Fortunately, your
own, unfounded opinion does not count for all developers.


PointedEars