Open Sourcing Quick Tree — A Fast JS Tree Library

Pranav Sharma
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.

What happens when you focus?
What happens when you focus?
Focus Mode at work.

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 libraryhttps://www.npmjs.com/package/quick_tree

Repository Codehttps://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.

The Startup

Medium's largest active publication, followed by +721K people. Follow to join our community.

Pranav Sharma

Written by

I am a software developer with some skills spread out to soccer, boxing and badminton.

The Startup

Medium's largest active publication, followed by +721K people. Follow to join our community.

Pranav Sharma

Written by

I am a software developer with some skills spread out to soccer, boxing and badminton.

The Startup

Medium's largest active publication, followed by +721K people. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store