5
\$\begingroup\$

I do not like this implementation as is seems too much complicated. My idea was to implement some BFS algorithm variant.

Some points to notice:

  1. I use one queue.
  2. In the begining put the tree root in the queue and dummy treeNode delimiter which is recognized by its data == -1.
    (I need this for distiguishing between tree levels).
  3. After each level I assign -1 to the queue.

Any suggestions of how to simplify it? (Currently seem to work good)

public void printTreeByLevels() // Should be BFS variant implementation
{
    int levelCounter = 0;
    boolean currNodeHasChild = false;
    Queue<TreeNode> q = new ArrayDeque<TreeNode>();

    q.add(m_Root);
    q.add(new TreeNode(-1));
    System.out.print("Level:" + levelCounter+ " ");

    while (!q.isEmpty())
    {
        TreeNode currentNode = q.poll();
        currNodeHasChild = false;
        if(currentNode.m_Data == -1)
        {
            TreeNode nextQueueNode = q.peek();
            while(nextQueueNode!= null && currentNode.m_Data == -1)
            {
                currentNode = q.poll(); //bypassing delimiters        
            }                        

            if(currentNode.m_Data != -1)
            {
                levelCounter++;
                System.out.println();
                System.out.print("Level:" + levelCounter+" ");
            }
            else if(nextQueueNode == null)
            {
                break;
            }

        }            

        System.out.print("\t"+currentNode.m_Data);

        if(currentNode.m_LeftNode!= null)
        {
            q.add(currentNode.m_LeftNode);    
            currNodeHasChild = true;
        }

        if(currentNode.m_RightNode!=null)
        {
            q.add(currentNode.m_RightNode);
            currNodeHasChild = true;
        }            

        if(currNodeHasChild)
        {
            q.add(new TreeNode(-1)); // sign of next level
        }                        
    }
}
\$\endgroup\$
2
\$\begingroup\$

General Notes

Let me preface this section with the fact that I have not looked at Java conventions in a while. Some of these suggestions may stray from classic Java conventions.

With that off my chest, visually your code looks pretty good, though mixture of underscores in your hungarian notation is a little bit odd (Thanks Vogel612).

// Could you not just have 'currentNode.mRightNode'?
if(currentNode.m_RightNode!=null)

You also have several loops or if-statements with only a single line of code in them. This may just be preference, but if you remove the braces in those cases:

if(currNodeHasChild)
{
    q.add(new TreeNode(-1)); // sign of next level
}

becomes

if(currNodeHasChild)
    q.add(new TreeNode(-1)); // sign of next level

which makes the code more compact without reducing readability.


NOTE: When using no-brace notation, only ONE LINE after the if-statement, for-loop, etc. will be considered 'inside' that block of code. As Vogel612 pointed out in a comment below, there have been cases where this notation was misused. Keep an eye out for these bugs, as they can pop up relatively easily.


One final thing: I do not prefer in-line comments. To my eyes, they break up the flow of the program visually.

BFS Solution

Now onto code improvements.

This problem is built to be solved by recursion. Combining recursion and a breadth-first search yields a relatively simple solution:

public void printTreeByLevels(Queue<TreeNode> nodes, int level)
{
    System.out.println("Level " + level);

    // New queue to hold child nodes
    Queue<TreeNode> newNodes = new ArrayDeque<TreeNode>();

    // Loop through all nodes in the queue
    for(TreeNode node : nodes)
    {
        System.out.println("\t" + node.m_Data);

        // Add child nodes if they exist      
        if(node.m_LeftNode != null)
            newNodes.add(node.m_LeftNode);
        if(node.m_RightNode != null)
            newNodes.add(node.m_RightNode);
    }

    // Call this function again only if one or many child node(s) were found
    if(!newNodes.isEmpty())
        printTreeByLevels(newNodes, level+1);
}

A single for-loop and some if-statements solve this problem quite simply and easily.

NOTE: I originally wrote this in Python as its been a while since I wrote Java. However, the syntax should all be correct.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Interesting. I did not know about the Apple SSL bug. I will cede the point that the no-brace syntax is more prone to bugs than other syntaxes. However, I still stand by my recommendation. As with all alternate sytaxes (or all syntax for that matter), the no-brace syntax is a tool to be used to help simplify your code in certain situations. It is up to the programmer to know how to correctly use that tool and in what situations to use the tool. This, I believe, is one of the situations. \$\endgroup\$ – BeetDemGuise May 13 '14 at 13:43
  • 2
    \$\begingroup\$ +1 The recursive approach looks pretty lean. As for the braces... I used to be a no-bracer like you, and then I took an error to the knee. \$\endgroup\$ – JvR May 13 '14 at 17:52
1
\$\begingroup\$

Looking back at this, there is a better way to deal with it than I initially envisioned.

The -1 nodes are a bit hackish. You only ever have two lists/queues to keep: nodes that you are currently processing, and nodes you will have to process on the next run/level. So let's keep them in two seperate lists:

public void printTreeByLevels(Appendable out) throws IOException {
    int level = 0;
    List<TreeNode> children = Arrays.asList(m_Root);
    while ( !children.isEmpty() ) {
        final List<TreeNode> current = children;
        children = new ArrayList<>();
        level++;
        out.append("Level " + level + ":");
        for ( final TreeNode node : current ) {
            out.append("\t" + node.m_Data);
            if ( node.m_LeftNode != null ) {
                children.add(node.m_LeftNode);
            }
            if ( node.m_RightNode != null ) {
                children.add(node.m_RightNode);
            }
        }
        out.append('\n');
    };
}
|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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