Recursive search to delete n'th child in tree

Question

I have to implement a tree programming here. What I mean by tree programming is I have data stored in tree format. I have a parent object which will have child objects of same type the level of depth can go any long:

I am able to store objects in tree format and also able to display properly. I am facing problems when I have to filter some child nodes based on some conditions:

I have two question:

• is this code fine?
• is there anything wrong with design?

Plus, how can I handle removing child node in a tree where the child can be in any place?

package menu;
import java.util.List;
public class Links{
private String nodeName;
     private List<Links> children;

     public List<Links> getChildren(){
        return children;
     }

     public void setChildren( List<Links> children ){
        this.children = children;
     }

     public String getNodeName(){
        return nodeName;
     }

     public void setNodeName( String nodeName ){
        this.nodeName = nodeName;
     }
}




  package menu;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

import com.chartis.gp.support.util.BrokerSupportUtil;
import com.chartis.gp.support.vo.Links;
import com.chartis.kernel.user.UserVO;
import com.chartis.kernel.utils.Utils;

public class Utility{

    /* IN this class NavModel,CModel,CNode are some dummy classes
     * which help us read contents form some resources which are stored in dummy format
     * as Example of tree format stored data below is the example 
     *    tree
     *       child1
     *       child2
     *       child3 
     *              child3-1
     *                       child:q
     *                       child:r
     *                               child:a
     *              child3-2
     *              
     *       child4 
    */


    private static void populateChildLinks(NavModel navModel, Object objectNode, Links parent ){
        try{
            List<Links> childLinks = new ArrayList<Links>();
            Iterator it = navModel.getChildren( objectNode );
            while( it.hasNext() ){
                NavNode node = (NavNode) it.next();
                CNode contentNode = node.getContentNode();

                Links links = new Links();

                links.setNodeName( contentNode.getNodeName() );

                childLinks.add( links );

                if( navModel.hasChildren( node ) ){
                    populateChildLinks( node, links );
                }
            }
            parent.setChildren( childLinks );

        }
        catch( Exception e ){

        }

    }

    private static Links createCategoryLinks(String categoryLinkName){
        Links categoryLinks = new Links();
        categoryLinks.setNodeName( categoryLinkName );
        return categoryLinks;
    }

    public static Links setupLinks(String categoryLinkName,String name) {
        Links categoryLinks=null;
        CModel contentModel = new CModel();
        NavModel navModel = new NavModel();
        categoryLinks = Utility.createCategoryLinks( categoryLinkName);
        Object objectNode = contentModel.getLocator().findByUniqueName(name);
        if( objectNode != null ){
            if( navModel.hasChildren( objectNode ) ){
                populateChildLinks( navModel,objectNode, categoryLinks );
            }
        }
    }

              // This is where i am facing issue once i get list of links of childs 
        // i have to delete how can i find that particular child in the list
        // do i have to iterate through all the links and delete or  which 
        // way is better
    private static void filterLinks( Links parentNode,
            List<Links> childNodeList ){
        List<Links> filteredResourceList = new ArrayList<Links>();
        if(  childNodeList!=null ){
            Iterator<Links> childNodeIt = childNodeList.iterator();
            while( childNodeIt.hasNext() ){
                Links childNode = (Links) childNodeIt.next();
                if(childNode.getChildren().size() >0 ){
                    filterLinks( childNode, childNode.getChildren() );
                }

                boolean removeNode = filterContents( childNode);
                if(! removeNode ){
                    filteredResourceList.add( childNode );
                }

            }
        }
        Iterator<Links> filteredResourceIt = filteredResourceList.iterator();
        while( filteredResourceIt.hasNext() ){
            Links childNode = (Links) filteredResourceIt.next();
            parentNode.getChildren().remove( childNode );
        }
    }

    // Let us consider this as some dummy method which returns true or false based on some conditions
    private static boolean filterContents( menu.Links childNode ){

        return false;
    }
}


package menu;

public class TreeDisplay{
    public static void main( String[] args ){
        Links link = Utility.setupLinks( "SomeName", "ResiyrbceBane" );
        Utility.filterLinks( link, link.getChildren() );
    }
}

Once I have a list of objects, I have to delete since it is tree object. How canI delete a child? I know I have to do a recursive search, but how can I do that? Which way will I delete? In the above tree structure where I have commented in the code, how can I delete child:q?

Answer 1

It is not possible to test your classes, because of:

import com.chartis.gp.support.util.BrokerSupportUtil;
import com.chartis.gp.support.vo.Links;
import com.chartis.kernel.user.UserVO;
import com.chartis.kernel.utils.Utils;

But ok, the general idea is ( if we want to use recursion):

remove(child, tree):
    if tree.isLeaf: return false
    if tree.hasChild(child): tree.removeChild(child); return true;
    for all children of tree as subtree:
        if remove(child, subtree): return true;
    return false;

Methods you will most probably need:

public void addChild(Links child)
{
    children.add(child);
}

public boolean hasChild(Links child)
{
    return children.contains(child);
}

public boolean removeChild(Links child)
{
    return children.remove(child);
}

public boolean isLeaf()
{
    return children.size() <= 0;
}

@Override
public int hashCode() {
    final int prime = 31;
    int result = 1;
    result = prime * result + ((nodeName == null) ? 0 : nodeName.hashCode());
    return result;
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Links other = (Links) obj;
    if (nodeName == null) {
        if (other.nodeName != null)
            return false;
    }
    else if (!nodeName.equals(other.nodeName)) //hint: this only works if nodeName is unique! If not, use a unique static counter
        return false;
    return true;
}

Take a look at some of the tree-classes of java to see some typical methods.

And your method could look like:

public static boolean removeChildFromTree(Links child, Links tree)
{
    if (tree.isLeaf()) //we are at a leave, we can not delete any children anymore
        return false;
    if (tree.hasChild(child)) //we found it, quickly delete it
        return tree.removeChild(child);
    //we have to search all children
    for (Links subTree : tree.getChildren())
    {
        if (removeChildFromTree(child, subTree)) //try to delete on subtree
            return true;
    }
    return false;
}

Edit: Just to point out, this code is not for efficiency. It is written for clarity. Do not care about efficiency before you really have to.