Manipulating B+ Trees in AngularJS

28 Nov 2014, by Moe in Developer

Not so recently I ran into an interesting problem, I needed to be able to display a B+ tree in HTML using AngularJS. A B+ Tree is a tree with a variable number of children per node so I couldn’t hard-code to expect a certain number of children per node like a typical binary tree. The problem came with finding a way to render the nodes as needed on a case by case basis.

The first thing that comes to mind when dealing with a tree type data structure is recursion. You go down the tree and work your way back up to the root displaying whatever is needed as you go. Sounds simple enough but how do we accomplish that with an ng-repeat? Maybe I could create something like an ng-repeat to handle it but I’d rather recreate the ng-repeat code and extend it in my own directive but rather build something that utilizes ng-repeat.

After scouring the web I stumbled upon to a great discovery, which is that ng-include can be used to include the document it resides in. For example, I have a template with some code and within that template I can use ng-include to include the template itself like so:

<script id="include.html" type="text/ng-template">
             This is a test.
             <div ng-init="btree = item.nodes" ng-include="'include.html'"></div>

The above code would just go on forever but you get the idea.

Now to put this discovery to good use we need to setup some rules and ways to check our nodes for children and such. We also need a good way to display the data in case we need to add some features to it later like edit, delete, add, etc. I created an example to see some of the possibilities here:

In the above example I made the list collapsible without any additional JavaScript, purely HTML and AngularJS. We can leverage the fact that when we use ng-include or ng-repeat, AngularJS creates a local scope to create local variables so we don’t even need to add JavaScript to create an expand collapse, edit, delete, etc.

In conclusion, despite it seeming like a daunting task in plain Javascript and HTML, the ability to manipulate something as complex as a B+ Tree in AngularJS is fairly simple though it may not be at first glance and with minimal code to boot.