Which tree implementation is better?

Question

Algorithms

At the university, I was taught to make a tree like this: Node(id, parent_id), and my grandfather Laforet teaches me to do this: Node(id, child_left_id, child_right_id).
The first solution seems to be more elegant (fewer fields) and more versatile (you can make as many descendants as you like without changing the data structure). But why then did such an authoritative comrade choose the second option?
What do you think is the best option?

Answer 1

It all depends on why you need this tree.
1. This is an Adjacency List , it is good when you need to write to the tree often and rarely read it.
2. This is a Nested Set , it is good when you need to read the tree often and rarely write to it.
In order to build a part of the tree according to the first option, you either need to pull out ALL records from the database, and then recursively go through them and build it, or write a built-in procedure so that the recursion is on the database side. You also need to make sure that there are no cyclic dependencies in IDs.
The second option can pull out a part of the tree with all its children in one request, but queries can be heavy when the structure changes , especially when the tree is large.
Personally, I use the first option for the comment tree and the second for the site menu. Although trees always make sense to cache.

Answer 2

Different types of trees exist because cases are different. And there are an order of magnitude more tree storage types than you know. For each case, its optimal implementation.
Which is better tomato or ass? What to eat - a tomato, what to s..t - ass. So stop looking for better options until there is a project.

Answer 3

You haven't heard about Nested Set and Materialized Path yet.