N-ary Tree Structures and Their Application for a Decision System

An n-ary tree structure is essentially a slightly more complex binary tree structure. We have one root node from which n children nodes go forth and from those children nodes their own children nodes. How can this help us with a question-and-answer decision system in a specific situation?

We need to make a simple application that can store these questions and answers and combine and connect them somehow in a relational database like MySQL. We would start, for example, like so:

1. Questions table

We could make a simple table to hold our questions with four columns of id, content, slug, and description. Content would represent the question itself, the slug, and the description if needed to show some additional information about the question. The questions will be the root nodes (or, better said, the node's content, but we will get into that later) in our structure on every second level and on the very first and a child node of an answer.

Next, we would get a request to add answers for our questions which we could approach like so:

2. Answers table

Our answers table would hold three columns of id, content, and slug. The answers will be the children nodes of our questions, and their number is not limited (hence the n-ary).

We have two simple tables to hold our questions and answers, but what are we aiming for next? Next, we want to connect the two and reproduce something like:

3. Our envisioned structure of questions and answers

Our leaf nodes (nodes that do not have children) would mean we have answered all relevant questions in the chain, which also means that we would have to be careful never to allow our question nodes to end up as leaf nodes.

How do we set up the next part so that the questions and answers interact and can form these chains?

4. Connecting tables between questions and answers

This would be our resulting structure, but of course, some fields are optional and are just cosmetic or, depending on the requirement on hand, needed or unneeded. The order column can be used to sort our answers.

We mentioned earlier that the questions and answers are the content of our nodes but not the nodes themselves. Suppose we have answers and questions that are often repeated, like Yes, No, or some questions. We wouldn't want the user to create new copies of answers and questions constantly. However, we would want to have, let's say, fifty answers and ten questions but still be able to create a tree structure of millions of elements and, with one edit, change that question or answer throughout the whole structure. That is where our transitions come into play. The transitions essentially represent our nodes, and their purpose is only to keep the structure orderly and show the content of the answer or question. Considering needs, we could remove the previous_question_transition_id and the previous_answer_transition_id from the tables but let us keep them and show some uses.

Let us put this into perspective, considering the prior image of our structure.

5. Our envisioned structure of questions and answers with data

As mentioned before, our transitions represent our nodes. With this implementation, we would need to have unique transition elements required for potential features we would implement. Still, we could use the same question and answer elements without limit and not have to copy anything.

The current_question_transition_id is the current asked question to which one of the answers is the answer represented by the answers_id foreign key inside the answer transition. The next_question_transition_id field links to our next question transition, and after selecting an answer, we would know what the next question is.

Let's expand on this and mention how a user could benefit from this and how an admin could edit and control this tree.

We will present our user with a starting question to which he has n number of answers. Upon choosing one, he goes to the next question with its answers. What if we wanted to track the user's answers and keep them for later? That is not an issue, as we have a neat trail laid out through the tree.

What if our admin wanted to change the answer or question on one of the nodes?

No issue, as he could create a new answer or question and switch the questions_id or answers_id on one of the transitions. What if he wanted to create mid tree branch, a new question-and-answer transition. He could do this simply by creating a new question transition, setting it to be the next_question_transition_id of some answer, attaching answer transitions to the question transition, and linking the answer transitions to new question transitions. Adding new questions to leaf nodes is trivial, but we would never allow adding answer transitions. Even searching becomes simple as we could go through the tree branches and find our relevant question or answer. Deleting answer transitions when they are leaf nodes is also a trivial task while deleting a question transition is more challenging as we would need to remove the children nodes.

It becomes interesting when it is a transition mid branch, and you would need to decide to remove the whole branch or connect the previous answer transition to the next-in-line question transition. Even a fun feature of copy-pasting entire branches becomes a possibility where you would take the relevant question or answer transition and place it somewhere else. The problem is that you would need to create new transition elements for the old ones, or you would run into editing transitions and similar issues. Copy-pasting could be a very resource-intensive process considering you need to go through each branch from start to finish and recreate it.

Let us go a step further. We could attach additional resources to each transition if needed. For example, we want to keep color with the answers or an icon, or anything else really.

This article was a short overview of a potential application of n-ary tree structures for a problem of this kind. Surely others would have done it differently, and feedback is always appreciated.