CareerCup

we can have an array of hash maps here where a key can point to multiple enteries which can again point to a key in another hash map.

C# code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace DataStructuresClass
{
   
   class NTreeForTraversal
   {
      private TraversalNode _root;

      public NTreeForTraversal()
      {
         _root = new TraversalNode(0, 0, "root");
      }
      
      public void AddToTreeNode(int id, int parentId, string label)
      {
         AddToTreeNode(_root, id, parentId, label);
      }
      public void AddToTreeNode(TraversalNode currentNode, int id, int parentId, string label)
      {
         //TraversalNode newNode = new TraversalNode(id, parentId, label);
         if (currentNode == null) return;
         //TraversalNode currentNode = _root;
         if (parentId == currentNode.Id)
         {
            currentNode.addToChildrenList(id, new TraversalNode(id, parentId, label));
         }
         else
         {
            if (currentNode.Children != null)
            {
               foreach (TraversalNode node in currentNode.Children.Values)
               {
                  AddToTreeNode(node, id, parentId, label);
               }
            }
         }
      }
      public void Print()
      {
         Print(_root, 0);
      }
      public void Print(TraversalNode node, int level)
      {
         String printStr = null;
         if (node != null)
         {
            for (int idx = 0; idx < level; idx++)
               printStr += "\t";
               
            Console.WriteLine(printStr + node.Label);
            if (node.Children != null)
            {
               foreach (TraversalNode childNodes in node.Children.Values)
               {
                  Print(childNodes, level+1);
               }
            }
         }
      }
   }

   public class TraversalNode
   {
      private String _label;
      private int _id;
      private int _parentId;      
      private Dictionary<Int32, TraversalNode> _childrenList;
      
      public TraversalNode(int id, int parentId, String label)
      {
         _label = label;
         _id = id;
         _parentId = parentId;
         _childrenList = null;
      }
      public void addToChildrenList(int id, TraversalNode node)
      {
         if (_childrenList == null)
         {
            _childrenList = new Dictionary<int, TraversalNode>();
         }
         if (!_childrenList.ContainsKey(id))
         {
            _childrenList.Add(id, node);
         }
      }

      public Int32 Id
      {
         get { return _id; }
      }
      public Int32 ParentId
      {
         get { return _parentId; }
      }
      public String Label
      {
         get { return _label; }
      }
      public Dictionary<int, TraversalNode> Children
      {
         get { return _childrenList; }
      }
      public String ToString()
      {
         return _label;
      }
   }
   class Program
   {
      static void Main(string[] args)
      {

         NTreeForTraversal tree = new NTreeForTraversal();
         tree.AddToTreeNode(1, 0, "1.0");
         tree.AddToTreeNode(2, 1, "1.1");
         tree.AddToTreeNode(3, 1, "1.2");
         tree.AddToTreeNode(4, 1, "1.3");
         tree.AddToTreeNode(5, 1, "1.4");
         tree.AddToTreeNode(6, 0, "2.0");
         tree.AddToTreeNode(7, 6, "2.1");
         tree.AddToTreeNode(8, 6, "2.2");
         tree.AddToTreeNode(10, 3, "1.2.1");
         tree.Print();
         
         Console.ReadKey();       
      }
   }
 }

I believe trees, where each node has mulitple childrens are suitable.
We can print recursively in root -> all_childrens (like pre-order) fashion. Below is the code snippet of printing part of it

class Node {
  public:
   Node(std::string &a_tag_name) : tag_name_(a_tag_name) { }
   friend ostream& operator<<(ostream& os, const Node& a_node);
  private:
   std::string tag_name_;
   std::vector<Node*> child_node_;
};

ostream&
operator<<(ostream& os, const SdpNode& a_node)
{
    // Print attr-bute-value pairs first
    os << a_node.tag_name_ ;
    if(a_node.child_node_.size() == 0) {
      return;
    } else {
      // Recursively print the child nodes
      std::vector<SdpNode*>::const_iterator it2;
      for(it2 = a_node.child_node_.begin(); it2 != a_node.child_node_.end(); it2++) {
        os << (*(*it2));
      }
    }
    return os;
}