6
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ In case it is relevant (and so there can't be any implication of plagiarism), the article I was writing is linked at the end of this comment. I never used the recursive implementation in the end. rudikershaw.com/articles/whichsearch2 \$\endgroup\$ Aug 3, 2017 at 11:49

4 Answers 4

4
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Thanks for your feedback. I am not particularly happy with the TreeNode situation either but my article is already longer than I want it to be and I really want to avoid it being a discussion on ADTs. It would ideal if there were a standardised Node in the java.collections package but c'est la vie. As for the braces, I agree. I think I can squeeze them in. \$\endgroup\$ Sep 20, 2015 at 9:34
  • \$\begingroup\$ @RudiKershaw I thnk you have an interesting problem here... the purpose of your snippet is to discuss ADT in non-compilation form, which means you only need a type name that sounds like a tree, but is potentially a less-than-ideal implementation. If that's the case, why not just 'invent' a name for your snippet? I think someone who wants to know more about ADTs will want to know the right implementations as well... not just to simply borrow types that sounds right but doesn't act right. ;) \$\endgroup\$
    – h.j.k.
    Sep 21, 2015 at 9:46
  • 1
    \$\begingroup\$ @RudiKershaw also, I'm not sure if this is going to be terribly complicated for your illustration, but filesystem traversals can be candidates for showing depth-first searches, and in Java 7 you have a suite of file classes to do that. \$\endgroup\$
    – h.j.k.
    Sep 21, 2015 at 9:48
  • 1
    \$\begingroup\$ @h.j.k. As it happens, my article got too long just talking about binary search and exhaustive on their own. So I've split it into two articles. Which gives me space to demonstrate my own Node implementation when I talk about depth-first and breadth-first. The file system idea is an interesting on through. I think it demonstrates a great use case as well as solving the problem of having to show a Node implementation. \$\endgroup\$ Sep 21, 2015 at 10:18
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ I'm afraid children() has to return an Enumeration according to the TreeNode interface contract. \$\endgroup\$ Sep 20, 2015 at 9:42
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.