Multiway Trees

“Rien n’est plus dangereux qu’une idée, quand on n’a qu’une idée.”
Émile-Auguste Chartier

Abstract
In considering how to print a multiway tree in heirarchical fashion, this blog shows that there are many ways to represent a multiway tree in a data structure. A node with a pointer to a list of child nodes is not always the best.

Source Code: https://github.com/theSundayProgrammer/heirarchy_CPP

Problem
Consider a table of the of following form:
________________________
|parent_id|item_id|info|
________________________
where item_id is unique to every row and parent_id matches with an item_id of some row except for a special row called the root which has a special parent_id, say zero, that is not present as an item_id. It is required to print this table in an heirachical fashion as for example

Root
  Child1
    Subchild1
    Subchild2
    ...
    SubchildN
  Child2
    Subchild21
    Subchild22

The first solution is to convert the given linear data into a multiway tree and traverse the data in a pre-order fashion. This can be done by picking the root node and traversing the tree to pick all its immediate children and then recursively the children of the children, using a breadth-first or depth-first algorithm. Another way to do it would be to use a map (known as intermediate map henceforth) from the parent_id to an array of children. This can then be used to generate a multiway tree.

struct raw_child
{
    int id;
    content name;
    int parent;
};
struct Child
{
    Child(content const& name_): name(name_){
    }
    content name;
    std::vector<Child> children;
};

std::map<int, vector<Data>> list_children;
 void generate_map(raw_child const& child)
  {
    list_children[child.parent].push_back({child.id,child.name});
  }
Data& get_root(int k)
{
  return list_children[k][0];
}
Child generate_tree(Data const & root)
{
  auto item = list_children.find(root.id);
  Child parent(root.name);
  if (item != list_children.end())
  {
      auto& subs = item->second;

      for (auto& ch : subs)
      {
        parent.children.push_back(generate_tree(ch));
      }
  }
  return parent;
}

Another way to represent the intermediate map is using a multi-map as in C++ multimap or Ocaml Hashtbl.
Notice that since the sole purpose of the tree is print the data in a heirarchical fashion, it is possible to print the data using the same traversal as in generating a tree. Hence there is no need to generate the tree.

void print_tree(Data const & root, int tab_count)
{
  auto item = list_children.find(root.id);
  Child parent(root.name);
  if (item != list_children.end())
  {
      auto& subs = item->second;

    for (auto& sub : subs)
        print_tree(sub, tab_count+1);
 }
  return parent;
}  
 

Taking a cue from Chartier as quoted above I considered other ways to address the main problem which is to print the array data in a heirachical fashion. The brute force solution would to be start with the root and then traverse the array to print all its children and all their children recursively. Notice from the code below that if n is the number of rows the time complexity is O(n2) in terms of comparisons because each non-leaf item (one which is parent of at least one other item) takes n comparisons to print all its immediate children and each leaf node (one that is not a parent of any other) takes n comparisons to determine it is a leaf node.

void print_tree(
                raw_child const &root,
                int tab_count)
{
  int k;
  for (int i = 0; i < tab_count; ++i)
    std::cout << " ";
  std::cout << root.name  << std::endl;
  auto child = std::find_if(raw_children.begin(),
                            raw_children.end(),
                            [&](raw_child const &r) {
                               return r.parent == root.id; });
  while (child != raw_children.end())
  {
    print_tree(*child, tab_count + 1);
    child = std::find_if(child+1,
                         raw_children.end(),
                         [&](raw_child const &r) {
                            return r.parent == root.id; });
  }
}

To reduce that time complexity we could sort the array based on parent_id. This would reduce the number of comparisons to at most O(log(n)). Hence including the sorting this would take O(n.log(n)). In other words we have used a sorted array to represent a multiway tree as shown below

 void print_tree(
                raw_child const &root,
                int tab_count)
{
  int k;
  for (int i = 0; i < tab_count; ++i)
    std::cout << " ";
  std::cout << root.name  << std::endl;
  
  auto child =  std::lower_bound(std::begin(raw_children),
                                 std::end(raw_children),root,
                                [](raw_child const& a, raw_child const& val){
                                return a.parent parent == root.id)
  {
    print_tree(*child, tab_count + 1);
    ++child;
  } 
} 

 

Conclusion
There is more than one way to accomplish a programming task. Thinking of different ways helps in improving an existing solution.

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in C++, Data Structure, Software Engineering and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s