1
\$\begingroup\$

I wanted to write depth first search reversal iteratively in Java. Can someone review my code? I'm not that much interested in naming of the variables, but in the structure of the code, i.e. I don't need to mark the nodes as visited when I traverse binary tree, right?

public static void dfs(TreeNode root){
        if(root == null)    return;
        Stack<TreeNode> res = new Stack<TreeNode>();
        res.push(root);
        while(!res.isEmpty()){
            TreeNode top = res.pop();
            System.out.print(top.val + " ");
            if(top.right != null)
                res.push(top.right);
            if(top.left!= null)
                res.push(top.left);
        }
    }

Recursive version:

public static void dfs(TreeNode root){
        if(root == null)    return;
        System.out.print(root.val + " ");
        dfs(root.left);
        dfs(root.right);
    }
\$\endgroup\$

2 Answers 2

7
\$\begingroup\$

I don't need to mark the nodes as visited, when I traverse binary tree, right?

Well, is your code working even though you are not doing this right now? Then yes, you don't need it.

See also this question for a theoretical discussion about marking nodes as visited, and this question for a practical reason to mark nodes (it's not needed for a simple search, but it is needed when looking for paths).

Naming

Even though you are not that interested, it is important. It makes your code more readable, which helps reviewers review your code. If you don't really care about your code, why should we?

In this case, it's not really that bad (there aren't all that many variables), but I wouldn't even know what res was short for (rest? Like the rest of the nodes?); even nodes would be better.

Formatting

Just like naming, correct formatting makes code easier to read and thus easier to maintain and review. Again, your code is very short, so it's not all that bad, but your spacing is off and you should use curly braces even for one-line statements.

Printing

Your code isn't really testable or practical as it doesn't return a result, but just prints something. You should return true (or the node) or false instead if your using it as a search, and return a string/list/etc if your using it to traverse the tree and collect the content of the nodes.

\$\endgroup\$
1
\$\begingroup\$

I agree with all of the Tim's points, but I wanted to add that your first approach is not depth first search, but breath first. You're going through root, then all 1st level leafs, then second etc.

Second function (recursive one) has a typo - you meant to use dfs function call inside not dfs2, right? And the second one is depth first.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Because the OP is using a stack in the first version, it is depth-first. \$\endgroup\$ Commented Oct 12, 2014 at 21:54
  • \$\begingroup\$ Right. I missed that. \$\endgroup\$
    – sha
    Commented Oct 12, 2014 at 22:55

Your Answer

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

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