How to implement a Tree data structure with multiple roots

Question

I need to implement a Tree data structure which should have multiple roots, not just 1 root. Look at this scenario, suppose I have to implement Tree data structure for "Book contents". Which are "Chapters > Sections > Sub-Sections" etc. The major problem is: There are multiple roots here, chapter 1, chapter 2, chapter 3 and so on. The root node must definitely start from chapters, since the type of content and functions are same starting from those level.

What my Task requires:

• Tree with multiple roots
• The Nodes are Ordered on horizontal level among same parent
• It is a non-binary tree, meaning there can be any number of roots and any number of childs.

I have come with a solution, but I think it is a messy approach. I made one class like one would normally do for tree data structure. This class is "SimpleTree" which works for a single chapter as root node. To make multiple root nodes possible, I made another class "TopWrapperForSimpleTree". This top wrapper class has an Array in order to store multiple "SimpleTree" elements to it (Basically multiple roots). The messy part here is that I have to copy each function of "SimpleTree" and define it for the wrapper class as well. For example, a "Traversal Function" would traverse all the elements in the "SimpleTree". But now I have to implement a "Traversal Function" for "TopWrapperForSimpleTree" class as well where it would have to loop through all the Roots calling Traversal function on each of them and concatenating the result. The same goes for other functions like, finding a node, deleting a node etc.

To sum it all, I need a Tree Data structure which can have multiple roots. It should be ordered as well. The order is very important.

Image showing Tree with multiple roots

Answer 1

A "tree with multiple roots" is not a tree. When you consider each chapter to be a tree, then the collection of chapters is a forest. But you could just add a root node. Chapters belong to a Book, and the Book is then the root node.

You don't need a data structure for multiple roots. You need a data structure where nodes are multi-functional and can represent a book, a chapter, a section, ...etc without having to duplicate code. OOP is perfect for that (inheritance).

The idea is to define a class that has all the common features that all objects have in common. For instance, a book, a chapter, a section, ... all have a name, and they all can have "children". Iteration of a tree could be implemented as a method of this class.

Then a book would be an extension of this base class: a book can for instance have an author property. A section would also be an extension of the base class, but could have as extra property a page number. A chapter could be an extension of a section, as it also has a page number, but may in addition have a chapter number, ...etc.

Here is one of the many ways to do that. I use JavaScript here, but it works in a similar way in other OOP languages:

class Node {
    constructor(name) {
        this.name = name;
        this.children = [];
    }
    add(...children) {
        this.children.push(...children);
        return this;  // Return the instance, so method calls can be chained...
    }
    toString() {
        return this.name; 
    }
    * iter(depth=0) { 
        // A pre-order iteration through the whole tree that this node represents  
        yield [depth, this];
        for (let child of this.children) {
            yield * child.iter(depth+1);
        }
    }
    * iterWithout(depth=0) { 
        // A pre-order iteration through the whole tree that this node represents 
        // ...but excluding the node on which the original call is made: 
        for (let child of this.children) {
            yield [depth, child];
            yield * child.iterWithout(depth+1);
        }
    }
}

class Book extends Node {
    constructor(name, author) {
        super(name);
        this.author = author; // specific property for Book instance
    }
    toString() {
        return super.toString() + ", by " + this.author; 
    }
}

class Section extends Node {
    constructor(name, page) {
        super(name);
        this.page = page; // specific property for any section (also chapter)
    }
    toString() {
        return super.toString() + ", page " + this.page; 
    }
}

class Chapter extends Section {
    constructor(id, name, page) {
        super(name, page);
        this.id = id; // specific property for Chapter instance
    }
    toString() {
        return "Chapter " + this.id + ". " + super.toString(); 
    }
}

// Illustration of how it could be used:
function main() { // Demo
    let book = new Book("The Perfect Theory", "Pedro G. Ferreira").add(
        new Chapter(1, "If a Person Falls Freely", 1).add(
            new Section("The Autumn of 1907", 1),
            new Section("The Article in the Yearbook", 4),
            new Section("Isaac Newton", 6),
            new Section("Gravity", 9),
        ),
        new Chapter(2, "The Most Valuable Discovery", 12),
        new Chapter(3, "Correct Mathematics, Abominable Physics", 28),
        new Chapter(4, "Collapsing Stars", 47)
    );
    for (let [depth, item] of book.iterWithout()) {
        console.log("  ".repeat(depth) + item.toString());
    }
}

main();