Constructing a tree from a collection of nodes

help
1

I'm starting my first Rust project, a toy implementation of a PKM system backed by a SQLite database. The basic data model is a collection of pages which hold a tree of blocks which contain the text of my notes.

In the database, I have a blocks table, where each block has its content string, the key of the page it belongs to, a foreign key of its parent block if it has one, and a foreign key to its next sibling to represent the order of child blocks under a parent. While I'm not averse to changing this schema, I designed it this way so that as changes are made to the tree within the application, they can be reflected back to the database without much complex logic for updating a lot of different references. The database also has a pages table which stores a foreign key to the root block of the page.

With this structure I'm able to get the blocks for a page out of the database with a simple query, which are then stored internally as a Vec of BlockRow structs, containing the data from each row in simple datatypes. I then construct a page struct which takes ownership of the row and page data from the database and converts the Vec into a HashMap mapping block IDs to the BlockRow structs.

Finally I need to construct a general tree structure which will allow me to represent my notes in an outline form. Each block may have sub-blocks to an arbitrary depth, and each block is in a specific order relative to its siblings. To avoid borrow-checker issues I was running into initially, the tree itself will only contain block IDs, while the blocks themselves will remain fully owned by the aforementioned HashMap. With this in mind, the tree node struct looks like this:

pub struct Tree<T> {
    /// This node's value
    pub value: T,
    /// The children of the current node.
    pub children: Vec<Tree<T>>,
}

where T is i64. I know that my blocks contain all the information needed to build them into a tree structure, but between my shaky algorithm knowledge and being new to Rust, I'm stumped and need some direction.

My current partial implementation looks like this:

pub fn build_tree(&mut self) {
        // create a mirror of the block_data map with block IDs to keep track of blocks
        // which haven't yet been added to the tree
        let mut remaining_blocks: Vec<i64> = self.block_data.keys().copied().collect();
        let mut blocks_by_parent: HashMap<i64, Vec<i64>> = HashMap::new();

        for (block_id, block) in self.block_data.iter() {
            let parent_id = block.parent_id.unwrap_or(0);
            if let None = blocks_by_parent.get_mut(&parent_id) {
                blocks_by_parent.insert(parent_id, Vec::new());
            }
            blocks_by_parent.get_mut(&parent_id).unwrap().push(*block_id);
        }

        let mut tree: Tree<i64> = Tree {
            value: 0,
            children: blocks_by_parent.remove(&0).unwrap().iter().map(|block_id| {
                Tree {
                    value: *block_id,
                    children: Vec::new()
                }
            }).collect()
        };

        let mut subtrees: HashMap<i64, Tree<i64>> = HashMap::new();
        subtrees.insert(0, tree);

        for (parent_id, child_id_vec) in blocks_by_parent.iter_mut() {
            subtrees.insert(*parent_id, child_id_vec.iter().map(|child| {
                Tree {
                    value: *child,
                    children: Vec::new()
                }
            }).collect());
        }

    }

but this only really does a first iteration, where each block that has any child blocks is turned into a Tree containing its own block ID and a vector of its child block IDs. the next step is to connect these subtrees together and so on, but I'm getting totally lost.

Any help or hints would be really appreciated, as getting the structure out of the database and into a useful representation in memory feels like the crux of my project but I'm feeling like I can't make progress. For full context, you can take a look at the project here on my GitHub.

2

My suggestion would be to process nodes in topological order, from leaves to the root. This way when you're processing a node its parent will always be unprocessed and thus available to add the child to it.

4

This seems to be the solution I was having a hard time figuring out. I can determine which nodes are leaves, and give them parents. For each subsequent iteration I only care about the parents of the subtree parents on up. I will report back when I get the chance to try my hand at implementing this method.

5

I've been tinkering with this and I feel I'm getting closer to the finish line. However, with the simple tree I'm testing with I'm winding up with duplicate nodes. This seems to generally be because I'm iterating over subtrees with no regard for their depth, so I'm not going up the tree level-by-level but each iteration goes one level higher for each subtree. In this case it means that a subtree that reaches the root earlier has nodes that other subtrees need to be connected to, but the root of that subtree has already gone by and there's no longer direct access to that tree node.

So things are getting better, but I'm now thinking that I'll need to do more passes to de-duplicate tree nodes and that's seeming like a whole other can of worms. Here is my current implementation:

 fn get_leaves(&self, blocks_by_parent: &HashMap<i64, Vec<i64>>) -> Vec<i64> {
        let mut leaf_block_ids = Vec::new();
        
        for (block_id, _block) in self.block_data.iter() {
            // check that no block has this block as a parent
            if let None = blocks_by_parent.get(block_id) {
                leaf_block_ids.push(*block_id)
            }
        }

        return leaf_block_ids;
    }

    /// create a tree of Tree<usize> nodes representing the blocks of the page.
    /// Each node contains the ID of a block and a vector of child Tree<usize>
    /// nodes.
    pub fn build_tree(&mut self) {
        // hash map containing child block ID vectors for each parent ID
        let mut blocks_by_parent: HashMap<i64, Vec<i64>> = HashMap::new();

        for (block_id, block) in self.block_data.iter() {
            let parent_id = block.parent_id.unwrap_or(0);
            if let None = blocks_by_parent.get_mut(&parent_id) {
                blocks_by_parent.insert(parent_id, Vec::new());
            }
            blocks_by_parent.get_mut(&parent_id).unwrap().push(*block_id);
        }

        let leaf_block_ids = self.get_leaves(&blocks_by_parent);

        // key is tree parent ID, value is the subtree itself
        let mut subtrees: HashMap<i64, Tree<i64>> = HashMap::new();

        // attach the leaves to their parents
        for block_id in leaf_block_ids {

            // the data associated with the leaf block id
            let block = self.block_data.get(&block_id).unwrap();

            // the block ID of the parent of the current block
            let parent_id = block.parent_id.unwrap_or(0);
            
            if let None = subtrees.get(&parent_id) {
                subtrees.insert(parent_id, Tree { value: parent_id, children: Vec::new() });
            }

            let parent_tree = subtrees.get_mut(&parent_id).unwrap();
            parent_tree.children.push(Tree { value: block_id, children: Vec::new() });
        }

        // subtrees from subtrees will be joined into new subtrees here
        // attach subtrees to their parents up until they reach the root
        while subtrees.len() > 1 {
            let mut next_subtrees: HashMap<i64, Tree<i64>> = HashMap::new();
            for subtree_root_id in subtrees.keys() {

                let subtree = subtrees.get(subtree_root_id).unwrap().clone();

                // subtree with value 0 is already at the root
                if subtree.value == 0 {
                    next_subtrees.insert(0, subtree);
                } 

                // non-root subtree
                else {
                    let optblock = self.block_data.get(&subtree.value);
                    let parent_id;
                    match optblock {
                        Some(block) => {
                            parent_id = block.parent_id.unwrap_or(0);
                        }
                        None => {
                            parent_id = 0;
                        }
                    }

                    match next_subtrees.get_mut(&parent_id) {
                        Some(parent_subtree) => {
                            parent_subtree.children.push(subtree);
                        }
                        None => {
                            next_subtrees.insert(parent_id, Tree {
                                value: parent_id,
                                children: vec![subtree]
                            });
                        }
                    }
                }
            }

            subtrees = next_subtrees;
        }

        self.block_tree = subtrees.get(&0).unwrap().clone();



        let tree_vec: Vec<&i64> = self.block_tree.dfs_preorder_iter().collect();
        println!("{:?}", tree_vec);
    }

I've been testing this against a set of nodes that should produce a tree that looks like the following diagram, where node 0 is a pseudo node because my actual data may have multiple nodes at the "root" level

     0   
    /
   1
  /  \
2     3
        \ 
         4

What I'm getting instead is a tree that looks like this:

     0   
    /  \
  1     1
 /       \
2         3
           \ 
            4

stepping through with a debugger shows that since we reach the root from the 2 leaf before reaching the root from the 4 leaf, the 1 node isn't available to attach to because the current iteration has already passed that level by.

I think I have some ideas to fix this, but I get the feeling that the borrow checker will get in my way if I try to keep multiple references to tree nodes even temporarily. Once again I would really appreciate a nudge in the right direction if there are any idiomatic solutions that I might be overlooking. At the end of the day, this portion of my application isn't totally performance-critical, but I'm enjoying the learning experience of thinking through algorithms in Rust.