Create a tree structure (for table of contents) from an array in Java

Question

I have an array of strings that come from html tags ....

String[] Headers = {"H1", "H1", "H2", "H3", "H3", "H2", "H2", "H3", "H4", "H2", "H2", "H2", "H1", "H2", "H2", "H3", "H4", "H4", "H2" };

I need to turn into a tree structure. Where any Hn is a child of the last Hn-1

ROOT
    H1
    H1
    ...H2
    ......H3
    ......H3
    ...H2
    ...H2
    ......H3
    .........H4
    ...H2
    ...H2
    ...H2
    H1
    ...H2
    ...H2
    ......H3
    .........H4
    .........H4
    ...H2

This is similar to what needs to be done with recursion and something that when I see the solution, I'm going to kick myself for not thinking about it before. Has anyone got a solution for me?

Update

So, I tried several recursion options with absolute luck. As it turned out, I made this problem harder than it was.

Due to the test case that appeared,

String [] Headers = {"H1", "H1", "H3", "H3", "H5", "H4", "H4", "H4"};

bcorso, :

private void addChildren(TocItem root, Elements headers) {
    if(headers == null || headers.size() == 0) return;

    Map<Integer, TocItem> mostRecent = new HashMap<Integer, TocItem>(headers.size());

    int startLevel = getTagLevel(headers.get(0)) - 1;
    mostRecent.put(startLevel, root);

    for(int i = 0; i < headers.size(); i++) {
        Element htag = headers.get(i);
        int level = getTagLevel(htag);
        TocItem next = new TocItem(htag, level);

        int offset = 1;
        TocItem parent =  mostRecent.get(level - offset);
        while(parent == null && offset < level) {
            offset++;
            parent = mostRecent.get(level - offset);
        }
        if(parent != null) {
            parent.addChild(next);
        }
        mostRecent.put(level, next);
    } 
}

Answer 1

Ideone. :

public static class Node{
    int level;
    List<Node> children = new ArrayList<Node>();
    Node(int level){ this.level = level;}
}

public static void main (String[] args) throws java.lang.Exception{
    String[] h = {"H1", "H1", "H2", "H3", "H3", "H5", "H2", "H2", "H3", "H4",
                  "H2", "H2", "H2", "H1", "H2", "H2", "H3","H4", "H4", "H2"};

    Node[] mostRecent = new Node[6];                      // 5 headers + 1 root tag.
    mostRecent[0] = new Node(0);                          // root tag (level = 0)

    for(int i = 0; i < h.length; i++){
        int level = Integer.parseInt(""+h[i].charAt(1));  // get tag "level"
        Node n = new Node(level);                         // create Node for tag
        mostRecent[level] = n;                            // update most recent tag

        int pLevel = level - 1;                          
        while(mostRecent[pLevel] == null) --pLevel;       // find nearest parent
        mostRecent[pLevel].children.add(n);               // append tag Node to parent

        for(int j = 1; j < level; j++)                    // print tag with indention
            System.out.print("\t");
        System.out.println(h[i]);
    } 
}

---

:

O(n) , h H1, H2, H3 H4, Node[].

node Hi . , node "H1" mostRecent[1] (, 0 ).

. . Ideone.

Answer 2

ya go:

class Example
{
    static class Node
    {
        final String name;
        final int indent;
        Collection<Node> children = new LinkedList<> ();

        Node (final String name)
        {
            this.name = name;
            this.indent = Integer.valueOf (name.substring (1));
        }
        Collection<Node> getChildren ()
        {
            return Collections.unmodifiableCollection (this.children);
        }
        void addChild (final Node child)
        {
            this.children.add (child);
        }
        @Override
        public String toString ()
        {
            final StringBuilder sb = new StringBuilder ();
            for (int i = 0; i < this.indent; i++)
                sb.append ("   ");
            sb.append (this.name).append ('\n');
            for (final Node node : this.children)
                sb.append (node.toString ());
            return sb.toString ();
        }
    }

    List<Node> contents = new LinkedList<> ();
    ArrayList<Node> stack = new ArrayList<> ();

    public void add (final String[] headers)
    {
        for (final String h : headers)
        {
            final int n = Integer.valueOf (h.substring (1));
            final Node node = new Node (h);

            while (this.stack.size () > n - 1)
                this.stack.remove (this.stack.size () - 1);

            if (n == 1)
            {
                this.contents.add (node);
                this.stack.add (node);
            }
            else
            {
                this.stack.get (n - 2).addChild (node);

                if (this.stack.size () < n)
                {
                    assert (this.stack.size () == n - 1);
                    this.stack.add (node);
                }
            }
        }
        this.stack.clear ();
    }

    @Override
    public String toString ()
    {
        final StringBuilder sb = new StringBuilder ();
        for (final Node node : this.contents)
            sb.append (node.toString ());
        return sb.toString ();
    }
}

:

    final Example ex = new Example ();
    ex.add (new String[] {"H1", "H1", "H2", "H3", "H3", "H2", "H2", "H3", "H4", "H2", "H2",
            "H2", "H1", "H2", "H2", "H3", "H4", "H4", "H2"});
    System.out.println (ex);