sschuldenzucker
Hey all, I’m building my own little app (side project) and I’m looking for a tree data structure. I’m honestly wondering if I’m overlooking something but I couldn’t find a library that’s right for me.
The whole thing should be “generic” (think, like a DOM), i.e., like this:
- Arbitrary number of children per node.
- Children are ordered.
- Easy to traverse. E.g. there should be “get sibling right after this”, “get parent” etc.
- Effiiciently find child by node ID (no zipper; I wanna build a microservice that manages the tree)
I could use a digraph from Erlang but it’s actually too flexible for my use case and would require a wrapper around it to make sure nobody’s creating a loop.
In particular 5. seems hard to satisfy with the libraries I found.
Do you guys agree that there’s currently no library that does this? Any advice on how I would build this without going crazy?
Thanks a lot!
Where Next?
Trending in Questions
Other Trending Topics
Latest on Elixir Forum
Sponsor Spotlight
Deploy Phoenix to your own VPS with PaaS ease: push-to-deploy, zero downtime, auto SSL, managed Postgres. 14-day free trial at potions.io
Categories:
Sub Categories:
Forums
Popular Tags
- #ecto
- #liveview
- #troubleshooting
- #learning-elixir
- #library
- #deployment
- #erlang
- #testing
- #genserver
- #mix
- #absinthe
- #remote-other
- #otp
- #plug
- #how-to-question
- #macros
- #postgres
- #elixirconf
- #channels
- #exunit
- #discussion
- #code-sync
- #podcasts
- #javascript
- #onsite
- #dialyzer
- #docker
- #authentication
- #umbrella
- #full-time-contract
- #podcasts-by-brainlid
- #ai
- #ecto-query
- #elixirconf-us
- #blog-post
- #elixir-ls
- #phoenix_html
- #iex
- #graphql
- #genstage
- #websockets
- #supervisor
- #advent-of-code
- #distillery
- #processes
- #elixirconf-eu
- #api
- #forms
- #metaprogramming
- #hex
Our Sponsors
Build Elixir applications with speed and confidence.
We build reliable cloud platforms for business-critical systems.
Catch errors, track performance, monitor hosts and more.
Error tracking, logs, uptime, and Just Enough APM. Built for developers.
Elixir, Erlang & BEAM conferences from Code Sync - join us in 2026!
Practical resources that improve the lives of professional developers.
Master modern tools, write cleaner code, and tackle real-world challenges.
The deployment platform built for Elixir: PaaS ease, VPS control.
The team behind Membrane, Popcorn, LiveDebugger. Available for hire.
Courses that'll move you from confusion to "Aha, now I get it!"
Showing Posts 1 to 5- Show Best Posts
- Show All (oldest first)
- Show All (newest first)
al2o3cr
Not sure I’m following the problem here - you can pass
:acyclicto:digraph.new/1and the library will handle enforcing that restriction.I only see 4 numbered bullet points, did something get lost in editing?
“Generic” is hard. Different implementations are going to have seriously different performance (both time and space) for specific operations.
For instance, a tree implemented as a closure table can answer queries like “what are all the descendants of this node” very efficiently. But moving a subtree in that implementation is very slow, because it needs to touch many rows for each element of the subtree.
An adjacency-list representation (aka “put a
parent_idcolumn on the record”) has the opposite properties: moving an entire subtree only needs to update theparent_idon the subtree’s root, but checking for descendants requires recursive CTEs or other SQL trickery.sschuldenzucker
Hey, thx for the pointers.
Regarding
:acyclic: This would definitely make it better but acyclic digraphs can still have undirected cycles (two nodes pointing to the same child), so it’s not enough. I guess you can get around that by restricting the access methods a bit more (e.g., don’t allow adding edges, just moving nodes).Oh, and in a digraph, the children of a node (aka. the edges going out of a node) are not ordered, right?
Regarding 5., this should’ve been 4. (no zippers).
Regarding “generic”, of course you’re right. I think for my use case, local operations (what’s the parent / next sibling / children / etc.; move this subtree somewhere else) should be enough. So adjacency lists are probably the way to go.
I suppose all of these things are not fundamentally hard, was just wondering if someone already did it.
petrus-jvrensburg
Would the Postgres Ltree datatype help?
sschuldenzucker
NB I’ve built something based on IDs (essentially doing the usual pointer rotations in a set of maps). Will publish something not too far out.
user20230119
Did you publish something?