TreeView - How to count all children (including co

Question

Is there a method to get the number of children in a TreeView object? I want to count all the children, including children's children, all the way down.

The getExpandedItemCount() method only gets the child count of children who are expanded. Is there a way to get the count of all the children regardless of whether they are expanded or not.

Answer 1

There is a good reason not providing a method to count all children of a tree, as the expanded tree size might be VERY large or even infinite.

E.g.: It is possible to display a tree of all digits of a 'real' number:

static class InfiniteNumberItem extends TreeItem<String> {
    boolean expanded = false;
    public InfiniteNumberItem(String name) {
        super(name);
    }

    @Override public ObservableList<TreeItem<String>> getChildren() {
        if (!expanded) {
            for (int i = 0; i < 10; i++)  {
                super.getChildren().add(new InfiniteNumberItem(""+i));
            }
            expanded = true;
        }
        return super.getChildren();
    }
    @Override public boolean isLeaf() {
        return false;
    }
}

void testTreeInfinite(VBox box) { 
    TreeView<String> tree = new TreeView<String>();
    tree.prefHeightProperty().bind(box.heightProperty());

    tree.setRoot(new InfiniteNumberItem("3."));
    box.getChildren().add(tree);
}

But if you know what you do, and if the tree is limited in (expanded) size, you have to count by your own:

int count(TreeItem<?> node) {
    int count = 1;
    for (TreeItem child : node.getChildren()) {
        count += count(child);
    }
    return count;
}

Answer 2

Use recursion, something like this:

private static <T> long countChildren(TreeItem<T> treeItem) {
    long count = 0;

    if (treeItem != null) {
        ObservableList<TreeItem<T>> children = treeItem.getChildren();

        if (children != null) {
            count += children.size();

            for (TreeItem<T> child : children) {
                count += countChildren(child);
            }
        }
    }

    return count;
}

To include the root within the tally, add 1:

long count = countChildren(treeItem) + 1;

Then just call the method giving the root as argument:

System.out.println(countChildren(treeView.getRoot()));

Answer 3

The solutions in this answer are overkill for just counting nodes in a small tree.

The simple recursive count solution in the other answers is fine. This answer is just provided to add a bit more context and alternate implementations.

On Stacks versus Recursion

When you use recursion, you are implicitly relying on the Java runtime to maintain a stack of items for you. For very large trees, this can be an issue, because the runtime can run out of stack space (a stack overflow).

For more information on preferring a stack over recursion see:

• John Skeet's answer to Java: Stackoverflow in finite recursion.
• Top coder tree traversal algorithms, depth first search.

Of course, if you know the trees you are processing are small in size, it is OK to use recursion. Sometimes recursive algorithms are easier to understand than their non-recursive counterparts.

Iterator Based Solution

private class TreeIterator<T> implements Iterator<TreeItem<T>> {
    private Stack<TreeItem<T>> stack = new Stack<>();

    public TreeIterator(TreeItem<T> root) {
        stack.push(root);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    public TreeItem<T> next() {
        TreeItem<T> nextItem = stack.pop();
        nextItem.getChildren().forEach(stack::push);

        return nextItem;
    }
}

Example usage of the Iterator to count the items in a tree.

TreeIterator<String> iterator = new TreeIterator<>(rootItem);
int nItems = 0;
while (iterator.hasNext()) {
    nItems++;
    iterator.next();
}

If desired, the iterator can be adapted to a stream, by creating a custom stream support class, which allows you to write functional code such as:

TreeItemStreamSupport.stream(rootItem)
    .filter(TreeItem::isExpanded)
    .count()

Sample program

import javafx.application.Application;
import javafx.geometry.Insets;
import javafx.scene.Scene;
import javafx.scene.control.*;
import javafx.scene.layout.VBox;
import javafx.stage.Stage;

import java.util.*;
import java.util.stream.*;

public class TreeViewSample extends Application {

    // limits on randomly generated tree size.
    private static final int MAX_DEPTH = 8;
    private static final int MAX_CHILDREN_PER_NODE = 6;
    private static final double EXPANSION_PROPABILITY = 0.2;

    public static void main(String[] args) {
        launch(args);
    }

    @Override
    public void start(Stage stage) {
        Label numItemsLabel = new Label();

        // create a tree.
        TreeItem<String> rootItem = TreeFactory.createTree(
                MAX_DEPTH,
                MAX_CHILDREN_PER_NODE,
                EXPANSION_PROPABILITY
        );
        rootItem.setExpanded(true);
        TreeView<String> tree = new TreeView<>(rootItem);

        numItemsLabel.setText(
            "Num Items: " + countExpandedItemsUsingStream(rootItem)
        );

        // display the number of items and the tree.
        VBox layout = new VBox(10, numItemsLabel, tree);
        layout.setPadding(new Insets(10));

        stage.setScene(new Scene(layout, 300, 250));
        stage.show();
    }

    // unused method demonstrating alternate solution.
    private long countItemsUsingIterator(TreeItem<String> rootItem) {
        TreeItemIterator<String> iterator = new TreeItemIterator<>(rootItem);

        int nItems = 0;
        while (iterator.hasNext()) {
            nItems++;
            iterator.next();
        }

        return nItems;
    }

    private long countExpandedItemsUsingStream(TreeItem<String> rootItem) {
        return
                TreeItemStreamSupport.stream(rootItem)
                        .filter(TreeItem::isExpanded)
                        .count();
    }

    // unused method demonstrating alternate Jens-Peter Haack solution.
    private long countItemsUsingRecursion(TreeItem<?> node) {
        int count = 1;

        for (TreeItem child : node.getChildren()) {
            count += countItemsUsingRecursion(child);
        }

        return count;
    }

    /**
     * Random Tree generation algorithm.
     */
    private static class TreeFactory {
        private static final Random random = new Random(42);

        static TreeItem<String> createTree(
                int maxDepth,
                int maxChildrenPerNode,
                double expansionProbability
        ) {
            TreeItem<String> root = new TreeItem<>("Root 0:0");
            Stack<DepthTreeItem> itemStack = new Stack<>();
            itemStack.push(new DepthTreeItem(root, 0));

            while (!itemStack.isEmpty()) {
                int numChildren = random.nextInt(maxChildrenPerNode + 1);

                DepthTreeItem nextItem = itemStack.pop();
                int childDepth = nextItem.depth + 1;

                for (int i = 0; i < numChildren; i++) {
                    TreeItem<String> child = new TreeItem<>(
                        "Item " + childDepth + ":" + i
                    );
                    child.setExpanded(random.nextDouble() < expansionProbability);
                    nextItem.treeItem.getChildren().add(child);
                    if (childDepth < maxDepth) {
                        itemStack.push(new DepthTreeItem(child, childDepth));
                    }
                }
            }

            return root;
        }

        static class DepthTreeItem {
            DepthTreeItem(TreeItem<String> treeItem, int depth) {
                this.treeItem = treeItem;
                this.depth = depth;
            }
            TreeItem<String> treeItem;
            int depth;
        }
    }
}

/**
 * Provide a stream of tree items from a root tree item.
 */
class TreeItemStreamSupport {
    public static <T> Stream<TreeItem<T>> stream(TreeItem<T> rootItem) {
        return asStream(new TreeItemIterator<>(rootItem));
    }

    private static <T> Stream<TreeItem<T>> asStream(TreeItemIterator<T> iterator) {
        Iterable<TreeItem<T>> iterable = () -> iterator;

        return StreamSupport.stream(
                iterable.spliterator(),
                false
        );
    }
}

/**
 * Iterate over items in a tree.
 * The tree should not be modified while this iterator is being used.
 *
 * @param <T> the type of items stored in the tree.
 */
class TreeItemIterator<T> implements Iterator<TreeItem<T>> {
    private Stack<TreeItem<T>> stack = new Stack<>();

    public TreeItemIterator(TreeItem<T> root) {
        stack.push(root);
    }

    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    @Override
    public TreeItem<T> next() {
        TreeItem<T> nextItem = stack.pop();
        nextItem.getChildren().forEach(stack::push);

        return nextItem;
    }
}