Search an element/item in an n-ary tree

Question

Search an element in a n-ary tree. Looking for good code practices, optimizations etc. If question is ambiguous, let me know and I will reply ASAP.

Note - SearchInANAryTree name of class is for personal maintenance reason, so please ignore feedback as that name does not sound good. Also, help me with three questions:

1. Constructor takes Array T[] items. Since we are using generics, is it considered good practice to use a list instead of an array?

2. As a corollary TreeNode nested static class is using a list, should it be replaced by an array?

3. Do we need exception-checking in TreeNode to ensure that its childNode is not greater than branching factor? Or can we trust private functions calling it no more than n-arry times?

 public final class SearchInANAryTree<T> {

        private TreeNode<T> root;

        /**
         * Constructs a tree with given branching factor (n-ary).
         * The integer arrays, which is specified in the BFS order.
         * For example, the children of the current node are
         * in position "nary * i + k" in the array, where i is the position of the current / parent node.
         * n-ary (nary) is the branching factor and k is the kth / count of the child.
         * 
         * @param items     the list of items, to be parsed according to branching factor.
         * @param nary      n-ary, the branching factor.
         */
        public SearchInANAryTree(T[] items, int nary) {
            if (nary <= 0) throw new NullPointerException("The branching factor : " + nary + ", should be greater than zero.");
            constructTree(items, nary);
        }

        private void constructTree(T[] items, int nary) {
            root = new TreeNode<T>(items[0], new ArrayList<TreeNode<T>>(nary));

            final Queue<TreeNode<T>> nodeQueue = new LinkedList<TreeNode<T>>();
            nodeQueue.add(root);

            for (int i = 0; i < (items.length / nary); i++) {
                if (items[i] != null) {
                    final TreeNode<T> node = nodeQueue.poll();

                    for (int k = 1; k <= nary; k++) {
                        if (items[nary * i + k] != null) {
                            TreeNode<T> childNode = new TreeNode<T>(items[nary * i + k], new ArrayList<TreeNode<T>>(nary));
                            nodeQueue.add(childNode);
                            node.childNodes.add(childNode); 
                        } 
                    }
                }
            }
        }

        /**
         * Search an element in the n-ary tree 
         * 
         * @param x         x is the item to search.
         * @return true     is item is found else false.
         */
        public boolean searchElement(T x) {
            final Queue<TreeNode<T>> nodeQueue = new LinkedList<TreeNode<T>>();
            nodeQueue.add(root);
            while (!nodeQueue.isEmpty()) {
                final TreeNode<T> node = nodeQueue.poll();

                if (node.item.equals(x)) return true;

                for (TreeNode<T> childNode : node.childNodes) {
                    if (childNode != null) {
                        nodeQueue.add(childNode);
                    }
                }
            }
            return false;
        }

        private static class TreeNode<T> {
            T item;
            List<TreeNode<T>> childNodes;

            public TreeNode(T item, List<TreeNode<T>> childNodes) {
                this.item = item;
                this.childNodes = childNodes;
            }
        }

        public static void main(String[] args) {        
            /*
             *               1 
             *           /   |   \
             *         2     3     4 
             *            /  |     | \
             *          5   6      8  10
             * 
             */
            Integer[] m1  = {1, 2, 3, 4, null, null, null, 5, 6, null, null, 8, null};
            SearchInANAryTree<Integer> sian2 = new SearchInANAryTree<Integer>(m1, 3);
            System.out.print("Expect: true, Actual: ");
            boolean result = true;
            for (Integer i : m1) {
                if (i != null)
                    result = result && sian2.searchElement(i);   // test case in a for loop.
            }
            System.out.println(result);


            System.out.println("Expect: false, Actual: " + sian2.searchElement(7));
        }
    }

Answer 1

I am taking a very broad stab at this, answering your questions along the way but with additional comments on the code in general.

        public SearchInANAryTree(T[] items, int nary) {
        if (nary <= 0) throw new NullPointerException("The branching factor : " + nary + ", should be greater than zero.");
        constructTree(items, nary);
    }

This is an incorrect use of NPE, consider using IllegalArgumentException. Given that you have included this in your code, did you consider the case where items is a null array?

Answer to question 1, There is no need to use a list, T[] is perfectly fine.

    private void constructTree(T[] items, int nary) {
    root = new TreeNode<T>(items[0], new ArrayList<TreeNode<T>>(nary));

    final Queue<TreeNode<T>> nodeQueue = new LinkedList<TreeNode<T>>();
    nodeQueue.add(root);

    for (int i = 0; i < (items.length / nary); i++) {
        if (items[i] != null) {
            final TreeNode<T> node = nodeQueue.poll();

            for (int k = 1; k <= nary; k++) {
                if (items[nary * i + k] != null) {
                    TreeNode<T> childNode = new TreeNode<T>(items[nary * i
                            + k], new ArrayList<TreeNode<T>>(nary));
                    nodeQueue.add(childNode);
                    node.childNodes.add(childNode);
                }
            }
        }
    }
}

This code generally is more complicated than it needs to be, when you are aware of the tree arity, the array is your tree representation, there is no needs to create the conceptual equivalent of how trees are represented on paper in code.

This code also has the following errors, using the example in the main function you have written

The array representation

Integer[] m1  = {1, 2, 3, 4, null, null, null, 5, 6, null, null, 8, null};

of the tree

 /*
  *               1 
  *           /   |   \
  *         2     3     4 
  *            /  |     | \
  *           5   6     8  10
  * 
  */

is converted to the tree

 /*
  *               1 
  *           /   |   \
  *         2     3     4 
  *            /  |   / |
  *           5   6  8  10
  * 
  */

by the code. You went from a correct literal representation on the tree in array form to an incorrect conceptual representation in code. You can correctly handle this with a NullObject tree node.

The remainder of the comments make the assumption that a node representation is desired over an array representation of the tree, as both your questions and my comments are not necessarily valid for an array representation.

A second error in your code is the case where you do not handle array representation where null root has children, did you consider error handling code for this scenario.

A third error is in the case of zero length array, since you have taken the care to address invalid values for nary, do you not want to handle 0 length arrays, which are valid trees with null root.

    private static class TreeNode<T> {
    T item;
    List<TreeNode<T>> childNodes;

    public TreeNode(T item, List<TreeNode<T>> childNodes) {
        this.item = item;
        this.childNodes = childNodes;
    }
}

Answer to the second question, Since you know the specific nary there isn't a need to use an array list. In practice however for small nary values less than 10 there is no great drawback or performance penalty for using an ArrayList, there is tho greater memory usage.

/**
 * Constructs an empty list with the specified initial capacity.
 *
 * @param  initialCapacity  the initial capacity of the list
 * @throws IllegalArgumentException if the specified initial capacity
 *         is negative
 */
public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this(10);
}

That is the constructor implementation from the JDK source and it is initialized with an array of size 10.

Brooks in his book Mythical man month says premature optimization is the root of all evil in programming, and it has long been the refuge of code that has been written without good understanding, in this case, I would definitely use an array, premature optimization claims or otherwise.

I did like that you made sure that TreeNode was static which is a common error that even experienced java programmers make.

On the 3'rd question, using an array will cause a runtime exception (ArrayIndexOutOfBoundsException) if one were to write code that attempts to insert more child nodes than the branching factor.

However, to answer your question, you can develop confidence that your private function behaves correctly with regards to branching factor. The way to develop this confidence is via writing some unit tests.