Depth First Traversal with Javascript

Question

I have been reading the following article: https://code.tutsplus.com/articles/data-structures-with-javascript-tree--cms-23393

This sets up the following classes and methods.

function Node(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
}

function Tree(data) {
    var node = new Node(data);
    this._root = node;
}

Tree.prototype.traverseDF = function(callback) {
    (function recurse(currentNode) {
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            recurse(currentNode.children[i]);
        }

        callback(currentNode);
    })(this._root);

};
var tree = new Tree('one');

tree._root.children.push(new Node('two'));
tree._root.children[0].parent = tree;

tree._root.children.push(new Node('three'));
tree._root.children[1].parent = tree;

tree._root.children.push(new Node('four'));
tree._root.children[2].parent = tree;

tree._root.children[0].children.push(new Node('five'));
tree._root.children[0].children[0].parent = tree._root.children[0];

tree._root.children[0].children.push(new Node('six'));
tree._root.children[0].children[1].parent = tree._root.children[0];

tree._root.children[2].children.push(new Node('seven'));
tree._root.children[2].children[0].parent = tree._root.children[2];

This tree looks like

 one
 ├── two
 │   ├── five
 │   └── six
 ├── three
 └── four
     └── seven

So when we finally make our traversal call

tree.traverseDF(function(node) {
    console.log(node.data)
});

It returns:

five
six
two
three
seven
four
one

This broke my understanding of "depth first". If you google depth first, wikipedia has the following image:

Under this picture it feels like the previous code should print:

one
two
five 
six

According to wikipedia:

One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking

The current implementation in this question, actually prints starting from the bottom, youngest children and moves up instead of top to bottom how its defined by wikipedia. Can anyone help me understand what I am missing?

trincot · Accepted Answer · 2018-02-04 20:43:56Z

4

Your code does perform a depth first search, but there is still flexibility in deciding when a node is to be considered "visited": is it on its first encounter, or while backtracking?

If you move your console.log before the loop, you'll get what you expected:

Tree.prototype.traverseDF = function(callback) {
    (function recurse(currentNode) {
        callback(currentNode); // <-----
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            recurse(currentNode.children[i]);
        }
    })(this._root);
};

There is no right or wrong here.

There are in fact three flavours. See Wikipedia:

pre-order (what you expected)
in-order (relevant for binary trees)
post-order (your version)

edited Feb 4, 2018 at 20:43

answered Feb 4, 2018 at 20:35

trincot

357k38 gold badges282 silver badges339 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

theamateurdataanalyst Over a year ago

May I ask how this is self terminating? Is it because when there are no longer children the for loop is bypassed and the callback is invoked? I forgot to ask this as part of the question.

trincot Over a year ago

It is self terminating because there is no recursive call on the leaves of the tree, which have no children, and so the loop does not have any iteration for those leaves. In that case the only thing that happens is the call of the callback function, and the recursion backtracks to the previous call. There the loop will go to its next iteration, ...etc.

Collectives™ on Stack Overflow

Depth First Traversal with Javascript

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related