Using AVL Binary Trees to Build a Smart Lists Sorter with React

It’s not that often that I get to use advanced algorithms or data structures in a frontend web app. But this time I did & it was really interesting!

The Problem

So I had the problem of sorting out my different backlog lists.

Lists like “Movies to watch”, “Games to play”, “Books to read”, …etc. Each time I wanted to add a new item to the list, I wouldn’t know where to place it exactly. So I throw it in a half-random spot.

The result? A list with no meaningful order.
(If this doesn’t sound like a big problem to you btw, maybe I should add that my lists usually contain 100+ entries 😅)

So one time I was thinking: "Can't this be done in a smarter way? Where I don't have to compare each new item I want to insert with most other items on the list before knowing where to put it?"

A certain algorithm came to mind!
Binary Search.

The Solution

If you haven't heared of Binary search before, then very breifly:
Think of searching for a word in a dictionary. You don't go through the words one by one; instead, you'd open to the middle and see if your word would be in the first half or the second, and repeat until you found your word.

That's binary search. (There's an important point here, the list (the dictionary in the above example) is sorted)

But Binary Search is used for searching for an item in a list, not inserting new items to it. Luckily, there's a data structure that is built on top of binary search but allows inserting new items.

This Data Structure is Binary Search Trees (BSTs for short).

BST is a data structure where each node has up to two children. The left child has a value less than its parent, and the right child has a value greater.
This makes it quicker to look up, insert, and delete items. O(logN)

They have a problem however...
The tree can become unbalanced. Meaning the left sub-tree of a node can get much longer than the right subtree.
So the complexity of the tree operations can go up from logN to N! Not good in my case.

Luckily again, there's another data structure built on top of BST, it's AVL trees.

AVL trees are self-balancing BSTs. They preserve the BST property while ensuring that the tree remains balanced at all times, keeping the complexity to O(logN).
This comes at the cost of increased code complexity, but well, I had no choice...

The Implementation

So behind the scene, I represent the sorted list of items the user has as an AVL tree instead of a normal array.
When he want to insert a new item to the list, I treat it like adding a new node to the tree. I start from the root & go down.
Comparing it with each node along the way to decide whether to go left or right.

But here comes the fun part: How do I know whether to go left or right??
This is a new item that the user just added & I have no idea whether the user likes it more or less than a certain other item on his list.
So I have to ask the user to compare the 2 items (the newly added item & the item of the node I'm currently on) & based on his choice, I either continue the tree traversal left or right.

Sounds complicated? Yes, I know.
This was challenging to implement. Especially the part where I had to mix the recursive algorithm logic (the insertion method) with async UI logic (Showing the user a modal & asking him to choose his prefered item).

It was indeed very "FUN" implementing that. 🥹

But no, really.
I learned a lot & enjoyed building something different this time. (Especially when it worked in the end, had it not worked, maybe my feelings would have been a bit different 🤣)

Here how the final flow of inserting an item looks:

The moral of the story?

Learning Algorithm & Data Structures (Even just the basics), is not a waste of time even to Frontend Developers.
It gives you more possibilities & better ideas you might otherwise don't think of. (I would never have had thought about this app’s idea if I didn’t know about Binary Search & AVL trees before)

The Links

If you wanna check out the app, here it is Sort My Lists App
And here is the app's code: Sort My Lists Github Repo

Let me know your thoughts in the comments below.

Until next time 👋