Building a tree from nodes with only depth and bottom-most children information

Question

I'm rewriting an old project. For arcane reasons (legacy corporation database, can't change), tree-shaped data is stored in the database in a peculiar way: each node has two properties defined: node depth, and a list of bottom-most depth child nodes.

How would I handle transforming that to a regular tree? I'm currently at the level where I have a set of all nodes to be placed in the tree, but I'm at a loss now. One thing I thought of is adding the nodes from the deepest level and going up to the root node, but that's a lot of messing with dangling nodes and resizing the tree.

EDIT: Just realised that my method would involve checking every combination of lower-level nodes to find one whose children sum equals to that of the higher-level one. Nope.

Answer 1

Just sort the nodes on depth and insert the nodes level by level.

There is only one root (depth 0 or 1, depending on your input), so the first step is easy.

At a generic step, you need to assign each node of the next level to the correct parent. The criterion is simple: the bottom-most children of the child node are a subset of the bottom-most children of the parent. If running time is not an issue, just check each child node against all parent nodes until you find a match. If that is too slow, please add a comment and I will think some more ;-)