Recursive TreeView Creation, Simplified

During my development of a web site mapper, I decided to save the information I recovered from each page in a BrotherTree. The BrotherTree is composed of BrotherNodes, initially defined as:

public class BrotherNode
    {

    private Uri             node_uri = null;

    private BrotherNode     parent = null;
    private BrotherNode     right_brother = null;
    private BrotherNode     left_brother = null;
    private BrotherNode     child = null;

Pictorially:

The BrotherNode is actually declared with additional fields, however, they are not germane to this article.

As each web page is encountered, its hyperlinks were collected using HtmlAgilityPack methods. The first hyperlink is stored in the current page's child BrotherNode. All additional hyperlinks are stored as the child's right-brothers. Adding a node to the BrotherTree was accomplished by the add_node method:

// ************************************************** add_node

public void add_node ( BrotherNode  parent,
                       BrotherNode  new_node )
    {

    if ( Root == null )             // root of BrotherTree
        {
        Root = new_node;
        }
    else
        {
        new_node.parent = parent;
        if ( parent.child == null )
            {
            parent.child = new_node;
            }
        else
            {
                                    // add as rightmost right
                                    // brother
            BrotherNode  node = parent.child;
            BrotherNode  next_node = node.right_brother;

            while ( next_node != null )
                {
                node = next_node;
                next_node = next_node.right_brother;
                }
            node.right_brother = new_node;
            new_node.left_brother = node;
            new_node.child = null;
            }
        }
    }

When all of the hyperlinks, from all of the web pages, had been collected, I had a BrotherTree that represented the web site.

Accessing the nodes in the BrotherTree is quite simple.

void traverse_tree ( BrotherNode node )
    {

    if ( node != null )
        {

        // do something with current node

        traverse_tree ( node.child );
        traverse_tree ( node.right_brother );
        }
    }

Although traversing a BrotherTree is quite simple, traversing a BrotherTree and building a TreeView from it proved to be somewhat problematic. In creating a TreeView, the parent of each new TreeNode must be used to insert the new TreeNode. I tried a number of different solutions, all of which were convoluted or complex. In an A-ha moment, the solution presented itself. Add a TreeNode to the BrotherNode, resulting in a revised BrotherNode that looks like:

public class BrotherNode
    {

    private Uri             node_uri = null;

    private BrotherNode     parent = null;
    private BrotherNode     right_brother = null;
    private BrotherNode     left_brother = null;
    private BrotherNode     child = null;

    TreeNode                tree_node;

Pictorially:

Now, when building the TreeView (tree_view_TV), we use the TreeNode in the BrotherNode to record the parent BrotherNode's place in the TreeView.

// ****************************************** create_tree_view

void create_tree_view ( BrotherNode node )
    {

    if ( node != null )
        {
        TreeNode  tree_node = new TreeNode ( node.NodeUri.
                                             AbsoluteUri );

        node.Tree_Node = tree_node;
        if ( node.parent == null )      // => the root
            {
            tree_view_TV.Nodes.Add ( node.Tree_Node );
            }
        else
            {
            node.parent.Tree_Node.Nodes.Add ( node.Tree_Node );
            }

        create_tree_view ( node.child );
        create_tree_view ( node.right_brother );
        }
    }

Adding a field to the BrotherNode reduced an otherwise complex TreeView creation to one that is relatively simple.

This solution once again supports the thesis that an increase in space complexity may significantly reduce time complexity.