Skip to content

Instantly share code, notes, and snippets.

@tylerneylon
Last active July 22, 2023 21:04
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tylerneylon/71d8b059e138664396d45dad1d1028ac to your computer and use it in GitHub Desktop.
Save tylerneylon/71d8b059e138664396d45dad1d1028ac to your computer and use it in GitHub Desktop.
A cute and simple way to print trees via console.log().
/* printTree.js
*
* A little function to print out a tree via console.log().
*
* The tree is expected to be an object whose keys (aka properties) are
* treated as nodes; each node mapping to an array of its children.
* Leaf nodes don't need to be present as keys.
*
* Here is an example tree with root element 'a':
* t = {a: ['b', 'c'], b: ['d'], c: ['e'], d: ['f', 'g'], g: ['h']}
*
* If you run printTree('a', t), you get this output:
*
* a - b - d - f - h
* \ g
* \ c - e
*
*/
// ______________________________________________________________________
// Functions
function showTableWithColumns(cols, topSep) {
if (topSep === undefined) topSep = ' ';
// Convert each cell to a string as needed.
cols = cols.map(col => col.map(x => x + ''));
let numRows = Math.max(...cols.map(x => x.length));
cols.forEach(col => {
while (col.length < numRows) col.push('');
});
// Find the maximum width in each column.
let widths = cols.map(col => Math.max(...col.map(x => x.length)));
let nonTopSep = ''.padEnd(topSep.length);
for (let i = 0; i < numRows; i++) {
let sep = (i === 0) ? topSep : nonTopSep;
let msg = cols.map((col, j) => col[i].padEnd(widths[j])).join(sep);
console.log(msg);
}
}
// Run fn1() and fn2() on each node of the given tree in depth-first order.
// Each call is of the form fn(node, depth, childNum).
// For the root, `childNum` is undefined.
// Otherwise, `childNum` is the index of this node as a child of its parent.
// fn1() is called before its children, fn2() after.
function depthFirstTraverse(root, tree, fn1, fn2, depth, childNum) {
if (depth === undefined) depth = 0;
fn1(root, depth, childNum);
tree[root]?.forEach((node, i) => {
depthFirstTraverse(node, tree, fn1, fn2, depth + 1, i)
});
fn2(root, depth, childNum);
}
// Print out a tree like this:
// 1 - 2 - 3 - 4
// \ 5
// \ 6
// \ 7 - 8
// \ 9 - 10 - 11
function printTree(root, tree) {
let cols = [];
let numRows = 0;
depthFirstTraverse(root, tree, (node, depth, childNum) => {
let prefix = '\\ ';
if (childNum === undefined) prefix = '';
if (childNum === 0) prefix = '- ';
if (cols.length <= depth) cols.push([]);
while (depth > 0 && cols[depth].length < cols[depth - 1].length - 1) {
cols[depth].push('');
}
cols[depth].push(prefix + node);
numRows = Math.max(numRows, cols[depth].length);
}, (node, depth) => {
while (cols[depth].length < numRows) cols[depth].push('');
});
showTableWithColumns(cols);
}
exports.printTree = printTree;
// ______________________________________________________________________
// Example usage
let t = {
a: ['j', 'b', 'ccc'], b: ['d'], c: ['e'],
d: ['f', 'g'], e: ['i'], g: ['h']
};
printTree('a', t);
@tylerneylon
Copy link
Author

This code is not designed to be the best-possible tree-printer, but rather a good trade-off between short/simple code and useful output. I always value simple code because it keeps the whole system easier to understand, debug, and work with — and is often faster. In particular, the tree-focused part of this is about 16 lines of code; it's short.

Here's the output if you run this:

a - j
  \ b   - d - f
            \ g - h
  \ ccc

There are a couple maybe non-obvious things happening.

The code knows to push down subtrees when an earlier tree has fewer descendants; an example is that the subtree of b is below whitespace in the top row.
The code also knows to skip rows when an earlier node has a large subtree that uses up rows below it; an example is that the node ccc has skipped a row to make room for the subtree of b.
Finally, it is tracking the column widths to keep the printout looking like a table. For example, the
node name ccc is longer, so it adjusts the full column to make room for that.

These things are obvious to a human but less obvious to code. :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment