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:
Constructor takes Array
T[] items
. Since we are using generics, is it considered good practice to use a list instead of an array?As a corollary
TreeNode nested static class
is using a list, should it be replaced by an array?Do we need exception-checking in
TreeNode
to ensure that itschildNode
is not greater thanbranching factor
? Or can we trust private functions calling it no more thann-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));
}
}