CodeSOD: Trim the Tree

Tis the season to think of trees.

Our Anonymous submitter has a program with a tree in it, and it's a relatively big one: 7 levels deep, with 200,000 leaf nodes. Oh, and it's managed in client-side JavaScript. In other words, it's the sort of thing you really want to make sure you're accessing efficiently.

Since it's a tree, and since in this case, all the nodes are doubly linked (each child contains a reference to its parent), it's easy to get from any one node to any other, with a minimal number of steps. There's never a good reason to traverse the entire tree.

Which is why Anonymous facepalmed when they found this code:

function matchWidget(root, widget, folder) { if (root.items) { root.items.forEach(item => { if (item.type === 'widget') { if (item.id === widget.id && item.parent.id === widget.parent.id ) { item.processed = true; updateParentCounters(item, folder); } } if (item.items) { return matchWidget(item, widget, folder); } }); return matchWidget(root.items, widget, folder); } return root;}

The purpose of this code is that as an item is "processed" in this application, the counter on all its ancestor nodes has to be incremented. There's a handy method already written for doing that, called updateParentCounters, which walks up the tree to the root node following the parent reference on each node.

That's not what this code does, of course. This code starts at the top of the tree. It looks at each possible root node (root is not a tree node, it's an object with an items property, and each of those is a root node for a different tree). It'll recursively walk down the tree, visiting every node. When it finds the node it's looking for, the recursion stops and it then calls updateParentCounters. The loop doesn't stop, so it'll search the other elements in root.items anyway.

The problem, of course, is that it already has the item it's looking for- widget is the item it wants. So the entire tree search can be replaced with updateParentCounters(item, folder). Which is exactly what our anonymous submitter did, vastly improving the performance of the application.

[Advertisement] Forget logs. Next time you're struggling to replicate error, crash and performance issues in your apps - Think Raygun! Installs in minutes. Learn more.