title: How to build a non-binary tree (with dependencies) incrementally
body: <h1>Short Description</h1>
  
  <p>I need to build a non-binary tree (language doesn't matter for now, but preferably in C++) from a list of items that do have dependencies to each other, but non-recurring and not cyclic.</p>
  
  <p>The data for the nodes are read from a file and incrementally inserted into the tree.
  The troubling part is how to handle those nodes which do not have parent-nodes yet that fulfill the dependency of the inserted node.</p>
  
  <h1>Detailed Description</h1>
  
  <h2>Rough Outline</h2>
  
  <p>The assignment is easy: represent a bunch of Tasks and Subtasks in a non-binary tree.
  This assignment would be quite easy to understand and implement, if not for a tiny condition: the list of Tasks has to be generated incrementally, so do the nodes in the tree.</p>
  
  <h2>Scenario</h2>
  
  <p>The Tasks are generated asynchronously and have to be added into the tree once the data to a certain Task is received.
  This is "simulated" by reading a csv-file which has a certain Task in each line with some data, the most important ones being the PID and PPID attributes.</p>
  
  <p>After a line is read and parsed, a Task is being created and inserted into the tree.
  The tree should automatically resolve the dependencies following two simple rules:</p>
  
  <ol>
  <li>Only show the node when the dependency is met (namely when a parent-node has been inserted before), but memorize the (now orphaned) node.</li>
  <li>Whenever a Task(node) is added, check if it's a parentnode of one of the above meantioned orphaned ones and reconcile the nodes if rule #1 isn't infringed while doing so.</li>
  </ol>
  
  <p>Please disregard the faulty logic behind this scenario: Normally, there can't be any SubTask without a ParentTask existing (at least in monolithic kernel designs).
  And while the List of Tasks certainly do contain the ParentTasks needed to model the tree, it is unknown <strong>when</strong> the ParentNode-Data is read and inserted into the tree.</p>
  
  <h2>Desired outcome</h2>
  
  <p>Below is a figure showing the "raw data", a list of (unsorted) Tasks which has been created incrementally while adding one Task after another to the list.
  The tree represents the subset of Tasks which has been inserted so far:</p>
  
  <p><a href="https://i.stack.imgur.com/yIYfg.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/yIYfg.png" alt="Figure showing the desired output"></a></p>
  
  <p>Please keep in mind that the tree is completely "naked" until the Tasks with the PIDs 1, 2 and 3 are inserted, because the other nodes are dependent of them.</p>
  
  <h2>What I did so far</h2>
  
  <p>I've written a Qt-C++ Code with three rough components:</p>
  
  <ul>
  <li>TaskTree which holds a Root-Node (a node without any task-data)</li>
  <li>TaskNode which has a field to hold the task-data and a <em>QList&lt;TaskNode&gt;</em> which is, in simple terms, a vector of TaskNodes to reference childnodes</li>
  <li>Task has the related attributes (like pid and ppid)</li>
  </ul>
  
  <p>It is no problem to insert a TaskNode if the parentnode already exists.
  This only works though in a perfect world, in which the Tasks are sorted upon their respective dependencies AND there's a determined amount of Tasks to be added.</p>
  
  <p>I don't have to tell you that such a scenario is highly unlikely though, so the tree creation has to memorize any orphaned node (which is a node that doesn't have a parent yet, duh).</p>
  
  <p>I've tackled this "memorization" in different ways, but failed alltogether because I couldn't wrap my head around the algorithms behind it.
  The two most promising thoughts I had were these:</p>
  
  <ol>
  <li>Insert every orphaned node into a vector. Upon inserting a parentnode, check if it has children in the Orphan-Vector and reconcile. Do this recursively for the newly created subtree to match all possiblities.</li>
  <li>Assign the PPID to the tree's RootNode, being 0 for the most top one. When an orphaned node appears, create a new TaskTree, assign the PPID of the orphan to the newly created tree and add the orphan to it.
  This creates subtrees which can be quit intricate themselfs if several orphans match one of the trees. After each inserted Node, try to reconcile the subtrees to the root-tree.</li>
  </ol>
  
  <p>Unfortunately I had to give up continuing those two concepts due to several spontaneous SIGSEGV's and other problems occuring because of the recursions etc.</p>
  
  <hr>
  
  <p>So in the end I'm here trying to find a way to actually make this work without cutting down the complexicity of the problem through assumptions and other cheats...</p>
  
  <p>Do you guys and gals have an idea which algorithm I could use for this problem or what category of problem this even is?</p>