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

Question

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

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

That I need turned into a tree structure. Where any Hn is the child of the most recent Hn-1

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

This feels like something that should be done with recursion and something that when I seen a solution I'm going to kick myself for not thinking of it sooner. Anyone got a solution for me?

Update:

So I had tried several variations of recursion with absolute no luck. As it turns out I was making this problem way harder than it had to be.

Because of a test case that came up,

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

I made a very slight tweak of bcorso's answer, here is what I ended up with:

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

Here is a working example on Ideone. The code is also below:

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's "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]);
    } 
}

---

Code Explaination:

It runs in O(n) time by simply walking though the list of headers h in a for-loop, and keeping track of the most recent H1, H2, H3, and H4, in an array, Node[].

The array is used to retrieved the most recent node of tag Hi by referencing it's level using the corresponding integer. For instance, the node with the most recent "H1" tag is retrieved using mostRecent[1] (note, element 0 is the used as the root of the whole document).

Note: If you need a dedicated function to print the tree see this Ideone.

Answer 2

Here 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 ();
    }
}

To use:

    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);