Java Recursive Depth First Search

Question

I've created a recursive depth-first search implementation in Java as an example for an article I am writing on my website. It needs to be concise in order to fit on the page easily (independent of screen sizes), hence the lack of extra spacing.

public static boolean depthFirstSearch(TreeNode find, TreeNode top){
   if(top == null || find == null) return false;
   else if(top.equals(find)) return true;
   Enumeration children = top.children();
   while(children.hasMoreElements()){
       TreeNode next = (TreeNode) children.nextElement();
       if(depthFirstSearch(find, next)){
           return true;
       }
   }
   return false;
}

I am using javax.swing.tree.TreeNode so that I don't have to include any custom node implementations and the search is only looking for the presence of a node, not position.

Answer 1

The context of this code example is not very clear, so in my remarks below I will suppose that the code is about a generic implementation of depth-first search.

TreeNode

If this is a generic implementation, my first question then is why TreeNode interface is there? This interface is part of Swing API, which has it own sphere of application. The objects implementing this interface may (or may not) be convenient here; anyway, they tend to be used in Swing/GUI-related situations and I'd not interfere with their scope for a generic case.

There is also something even more important concerning TreeNode. As you know, it has children() method which returns an Enumeration. This type is a very old Java thing (since JDK1.0), introduced even before Collections, and currently it looks like a rudiment. And it's not very pleasant to iterate on.

But if you still need/want to keep TreeNode, a type bound mark Enumeration<TreeNode> should be added, in order to avoid compilation warnings.

To replace TreeNode, I'd suggest to create a short and concise Node class, which points to a Collection (or even a Stream) of children Nodes and overrides hashCode and equals methods. This class would also be useful in other examples of your article.

Code Blocks

I understand that conciseness and lack of extra space is the priority in this code, but when I see this

if(top == null || find == null) return false;
else if(top.equals(find)) return true;

it looks for me more like code obfuscation. Please find a place to use braces:

if (top == null || find == null) {
    return false;
}
else if (top.equals(find)) {
     return true;
}

It can be very confusing and error-prone when the instruction that immediately follows a condition is not wrapped in a block.

Answer 2

Maybe for concise-ness, can you swap the enum to an iterable and try:

for (TreeNode child : top.children()) {
...  // Your code    
}

Saves 2 lines, but perhaps sacrifices too much clarity?

Your call, let me know what you decide.

Answer 3

Don't use swing's TreeNode. It's horrendous and outdated; it does not even use generics. Either write your own (not complicated) or try to find a library that is more recent than 2005.

Answer 4

Using recursion in this manner is fine for Tree structures but there is no guarantee that this won't be used for graphs. Given a graph with cyclic edges your recursion will run indefinitely (or at least until the stack overflows).

Instead build a Stack of the visited node that require visiting and mark checked nodes as checked as you go through. This way you can check the connections of all nodes and remove them from the stack as you go through without falling down into a spiral of infinite recursion.