Open Sourcing Quick Tree — A Fast JS Tree Library

Pranav Sharma

Follow

Jul 30 · 5 min read

Check out the JS library at — https://www.npmjs.com/package/quick_tree

Quick Tree is a JS library that can help you build an M-ary Tree and perform operations on it.

While working on an optimization effort for a legacy project, I struggled to find a JS library which was general and fast enough that could model a tree, so I wrote this small library as part of those enhancements.

Using this library, you can model a file system, traced hierarchical tasks, and all the binary tree applications.

Talking of Scale: Our trees ranged ~ 40k–50k nodes.

Do note that the tree can be highly unbalanced, and we don’t want to change its structure because of hierarchical relations between the nodes.

Use Cases

Some of the use cases/features that we wanted in the reshaped project are —

1. Display — Render the tree in UI. Using a UI framework.
2. Simple Search — Perform search on the tree for the text on nodes and get a refined tree. (If a node matches, we include all its children.)
3. Advanced Search — Store and perform search on custom metadata related to node, without manipulating underlying data structure.
4. Focus Mode — Get a rooted subtree from the tree and render at that level.
5. Proximity Search — Get siblings of a node.

Let’s see how we can accomplish all of these using quick_tree.

All the functions/routines discussed in the following use cases are implemented in the library.

As Input, we use an array of node data with two required fields “id” and “parentId”-

The library has a function which takes an array as on the left and returns a TreeNode.

We can store the output TreeNode in cache/in-memory/redux store. All the further operations can be performed only this root TreeNode.

The user doesn’t need to interact with TreeNode, she just needs to save it for passing it to the algorithms as the root.

Use Case: Focus Mode

If the tree is large, we would want to give the user an experience where she can “focus” on a subtree. For this, the user first selects (or searches and then selects) the node she is interested in, and then enters Focus mode.

Technically — What this means is we would want to render a sub-tree which has root key equal to the one user selected.

We use level order search, as we just want to return a node and return the matched node.

Use Case: Perform a Search

The user might want to search for a node in the tree based on the node text.

Technically — User enters a query and the tree updates based on the matched nodes. We discontinue search on children if a node matches the text.

We use DFS because we need to return a refined tree structure with the hierarchy intact. DFS recursively searches and returns the root node (with subtree to matches) if there is a match, else null.

If we are performing a real-time update to the rendered tree, it's better to put a minimum length limit of 3–4 characters as otherwise there will be lot of re-rendering.

Use Case: Chain Focus and Search

Let’s say the user want to incrementally dig inside the tree. What she can do is she can search for a term, click on the node, then enter focus, then search being in focus, then search and carries on.

Technically — This is not so different from chaining the two operations. While we render the tree, we keep the current_root of the focussed tree, and on search, we provide this current_root to the search algo. On further focus operations, this current_root is passed as root, and all works well.

Use Case: Proximity Nodes

The user might be interested in checking nodes in proximity of the current node in the tree. We define proximity as 1 parent, all siblings and children of that node.

Technically — In our data structure we don’t use parent pointers, because of language capabilities and the overhead.

We use BFS (level order) with 2 queues, which helps to keep track of siblings while we process the children of a node. If we find a match, we store all the sibling objects, and process the matched node to gets its child.

Use Case: Store Metadata

The user wants to store some metadata related to the tree in the tree data structure. She might also want to pre-process the data before storing. She can then perform queries/filtering based on these key-value pairs.

Technically — We want to give user a way to store metadata in the tree.

To store metadata, the buildTree function takes a second argument (which should be a function) and is applied to all the nodes. While applying that function to the nodes, it is passed the nodeList object corresponding to it as an argument. Please read here for more details - https://www.npmjs.com/package/quick_tree#buildtree

Use Case: Filter with Metadata

The user might be interested to filter the tree based on value of a meta key she provided while building the tree. Let’s say she wants the nodes which have meta as "key1": "value1"

Technically — This is like performing a search, but on an object, with matching a value to a key.

We perform DFS because we want to preserve the hierarchy and return the filtered tree to be rendered.

Use Case: Get Nodes in Subtree matched Metadata

Let’s say the user want to extract some stats from the tree based on the metaVals. She wants to collect all the nodes, in a subtree which match a condition on metadata.

Let's say we want to display the number of nodes with metadata having "status": "active". And we want to update this count as and when user clicks on a different node. Gist of it is displaying — count of “active” nodes in a subtree rooted at current_clicked_node.

Technically — We want to search and return all the nodes which match the metadata condition.

We perform a BFS, as we want to return the list of nodes (no hierarchy). We also can provide the limit in the function to stop searching and return the list when the matched nodes exceed the limit.

The redesign of the application helped us to introduce features like focus mode, stat display, and proximity search in an efficient way. It also reduced the number of operations hence reduced load times.

Link to the library — https://www.npmjs.com/package/quick_tree

Repository Code — https://github.com/phraniiac/quick_tree

All contributions to the repo are welcome. If you face any issues/lack of functionality, please raise an issue on GitHub.