Print a hierarchical tree structure in javascript

Question

I'm working on a problem where given an array of file paths I would like to print the file structure. For example with the given array ["/a/b/c", "a/a/a", "/a/b/d"], the ideal structure would look like :

a
 b
  c
  d
 a
  a

But my structure ends up looking more like this:

a
 b
  c
a
 a
a
 b

From what I can gather this is being caused by my tree not recognizing when a node already exists in a tree. So it is adding the node "a" three times as opposed to recognizing that an "a" already exists and traversing into it.

let paths = ["/a/b/c", "a/a/a", "/a/b/d"]

class TreeNode {
    constructor(value) {
        this.value = value;
        this.children = [];
    }
    
    addChild(element) {
        this.children.push(element)
    }
}

const head = new TreeNode('Head');
let cur = head;

paths.forEach(element => {
    cur = head;
    let filePath = element.split('/');
    filePath.shift();
    
    filePath.forEach(element => {
        let newNode = new TreeNode(element);
        if(!cur.children.includes(newNode)) {
            cur.addChild(newNode);
            cur = cur.children[cur.children.length - 1];
        } else {
            cur = cur.children.indexOf(newNode);
        }
    })
})

var spaceAppend = function(num) {
    let i = 0;
    let space = "";
    while(i < num) {
        space += " ";
        i++;
    }
    return space;
}

var traverse = function(node, level = 0){
    if(node === null)
        return;

    console.log(spaceAppend(level), node.value)
    if(node.children) {
        for(const n of node.children) {
            traverse(n, level + 1);
        }
    }
}

traverse(head)

Is there an issue with my tree implementation?

score 2 · Accepted Answer · answered Dec 16 '20 at 19:52

Some issues:

.includes() is not the right way to find a matching value. Use .find() instead.
.indexOf() will return an index, so that is not the right value you want to assign to cur in the else block.
shift may throw away an essential part of the path when it does not start with /. You can ease the processing by using .match() instead of .split(), so that you get exactly the non-empty parts of the path.

Less of an issue:

There is no need to define cur outside of the outer loop.
JavaScript has a native function for something like spaceAppend. You can use .repeat().
new TreeNode(element) is also called when you actually don't need it. Only create a new node when you know there is no matching node.
You could replace the inner .forEach() loop with .reduce(), which gives a better scope-handling for the cur variable.

Here is your code with those remarks taken into account:

class TreeNode {
    constructor(value) {
        this.value = value;
        this.children = [];
    }
    
    addChild(element) {
        this.children.push(element);
    }
}

let paths = ["/a/b/c", "a/a/a", "/a/b/d"];
const head = new TreeNode('Head');

paths.forEach(element => {
    // Use .match() to only get non-empty elements
    let filePath = element.match(/[^\/]+/g);
    
    filePath.reduce((cur, element) => {
        // Use .find() instead of .includes()
        let node = cur.children.find(child => child.value === element);
        // Only create the node when needed:
        if (!node) {
            node = new TreeNode(element);
            cur.addChild(node);
        }
        // Walk down one step in the tree
        return node; // ...becomes the value of `cur`
    }, head); // Initial value of reduction
});

const traverse = function(node, level=0) {
    if (node === null) return;
    // Use .repeat():
    console.log(" ".repeat(level), node.value);
    if (node.children) {
        for (const n of node.children) {
            traverse(n, level + 1);
        }
    }
}

traverse(head);

blake-g · Answer 2 · 2020-12-16T03:37:51.060

Is the starter array meant to be ["/a/b/c", "/a/a/a", "/a/b/d"] ("/a/a/a" instead of ("a/a/a")?

I think the crux of the problem you're having is the line

if(!cur.children.includes(newNode)) { ... }

When a new node is created, even if it has the same value as a previous one, it will not result in equity when comparing the two TreeNode objects. You need to compare the value of the nodes, not the nodes themselves.

So an example with a simplified version of your node object:

class TreeNode {
    constructor(value) {
        this.value = value;
    }
}

a1 = new TreeNode('a');
a2 = new TreeNode('a');

console.log("a1 == a2");
console.log(a1 == a2); // false

console.log("a1.value == a2.value");
console.log(a1.value == a2.value); // true

I adjusted the inner forEach loop with one that compares the values instead of the TreeNode objects

filePath.forEach(element => {
    let newNode = new TreeNode(element);
    let tempNode = null;
    for (var i = 0; i < cur.children.length; i++) {
      if (cur.children[i].value == newNode.value) {
        tempNode = cur.children[i];
      }
    }
    if (tempNode == null) {
      cur.addChild(newNode);
      cur = newNode;
    } else {
      cur = tempNode;
    }
});

Full code snippet on codepen

Object equality in javascript isn't particularly nice to deal with see this other answer for more information

Thank You! And yes, this is exactly how the problem was given to me. That's why I added the filePath.shift() to get rid of the preceding empty space — Magikly Delishis, Dec 16 '20 at 13:44
The [answer by trincot](https://stackoverflow.com/a/65330241/10672141) has some more information and better practices than mine I'd say, so make sure to check their answer too — blake-g, Dec 16 '20 at 21:41

score 0 · Answer 3 · answered Dec 30 '20 at 21:14

Here is a solution using lodash and object-treeify. While it's simpler code, there is obviously a trade-off introducing additional dependencies.

This solution works by first converting the paths into a tree structure and then visualizing it using object-treeify

// const lodash = require('lodash');
// const objectTreeify = require('object-treeify');

const myPaths = ['/a/b/c', 'a/a/a', '/a/b/d'];

const treeify = (paths) => objectTreeify(paths.reduce((p, c) => {
  lodash.set(p, c.match(/[^/]+/g));
  return p;
}, {}), {
  spacerNoNeighbour: ' ',
  spacerNeighbour: ' ',
  keyNoNeighbour: '',
  keyNeighbour: ''
});

console.log(treeify(myPaths));
/* =>
a
 b
  c
  d
 a
  a
*/

.as-console-wrapper {max-height: 100% !important; top: 0}

<script src="https://bundle.run/lodash@4.17.20"></script>
<script src="https://bundle.run/object-treeify@1.1.31"></script>

Disclaimer: I'm the author of object-treeify

Print a hierarchical tree structure in javascript

3 Answers3