How to get all leaf nodes of a tree?

Suppose I have a node in a tree, how can I get all leaf nodes whose ancestor is this node? I have defined the TreeNode like this:

public class TreeNode<T>
{
    /** all children of the node */
    private List<TreeNode<T>> children = new ArrayList<TreeNode<T>>();
    /** the parent of the node, if the node is root, parent = null */
    private TreeNode<T> parent = null;
    /** the stored data of the node */
    private T data = null;

    /** the method I want to implement */
    public Set<TreeNode<T>> getAllLeafNodes()
    {
        Set<TreeNode<T>> leafNodes = new HashSet<TreeNode<T>>();
        return leafNodes;
    }
}

Answers


Use recursion.

  • if the node itself is a leaf, return it
  • otherwise, return all the leaf-nodes of its children

Something like this (not tested):

public Set<TreeNode<T>> getAllLeafNodes() {
    Set<TreeNode<T>> leafNodes = new HashSet<TreeNode<T>>();
    if (this.children.isEmpty()) {
        leafNodes.add(this);
    } else {
        for (TreeNode<T> child : this.children) {
            leafNodes.addAll(child.getAllLeafNodes());
        }
    }
    return leafNodes;
}

Need Your Help

What's causing my c# WinForms application to freeze / hang?

c# multithreading winforms

I have a .Net 2.0 C# WinForms application that runs fine in development but occasionally freezes in production. I have looked for all the usual culprits:

Cufon, jquery text repacement

jquery cufon

I'm using cufon text replacing from Jquery