current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

I have come up with this code to do level order traversal recursively for a binary search tree. 

private void printLevelOrder_Recursive(Node root2) {
    Queue<Node> queue = new LinkedList<Node>();
    queue.add(root2);

    Stack<Node> stack = new Stack<Node>();
    stack.add(root2);
    if(stack.isEmpty() == false) {

        Node node = stack.pop();
        System.out.println(node.data);

        stack.addAll(printLevelOrder_Recursive_Children(node.left, node.right));
    }

    while(stack.isEmpty() == false) {
        Node node = stack.pop();
        System.out.println(node.data);
    }
}

private Stack<Node> printLevelOrder_Recursive_Children(Node left, Node right) {
    Stack<Node> stack = new Stack<Node>();
    if (left == null && right == null) {
        return stack;
    }

    Stack<Node> leftChildren = new Stack<Node>();
    Stack<Node> rightChildren = new Stack<Node>();
    if (left != null && (left.left != null || left.right != null)) {
        leftChildren = printLevelOrder_Recursive_Children(left.left, left.right);
    }
    if (right != null && (right.left != null || right.right != null)) {
        rightChildren = printLevelOrder_Recursive_Children(right.left, right.right);
    }

    if (rightChildren.isEmpty() == false) {
        stack.addAll(rightChildren);
    }
    if (leftChildren.isEmpty() == false) {
        stack.addAll(leftChildren);
    }
    if (right != null) {
        stack.add(right);
    }
    if (left != null) {
        stack.add(left);
    }
    return stack;
}

where Node is:

public class Node {
    public int data;
    public Node left;
    public Node right; 
}

I looked at various implementations, but I find mine much easier. Could you please chime in with your review and thoughts?

share|improve this question
1  
I assume this is java? I took the freedom to tag your question as such, if I am wrong.. please correct me ;) –  Vogel612 Jun 7 at 10:40

3 Answers 3

up vote 3 down vote accepted

Incorrect level order traversal

The implementation is not correct. It doesn't work for trees that are deeper than 3 levels.

The only reason it still works for 3 levels is that printLevelOrder_Recursive_Children looks ahead to its left-right children.

The reason why this just cannot work, is that printLevelOrder_Recursive_Children will recurse deep to its children, breaking the level order. There is nothing in your code to keep the traversal on a level, there's nothing to prevent from going too deep in a branch.

To demonstrate the problem, consider this tree:

        A
      B   P
   C        Q
D

The correct level order traversal should be: A, B, P, C, Q, D

But your implementation gives: A, B, P, C, D, Q,

To play with this, I modified the definition of Node a little bit, to make it work with Character data (or any other type too):

static class Node<T> {
    public T data;
    public Node<T> left;
    public Node<T> right;

    public Node(T data) {
        this.data = data;
    }
}

And created the example tree like this:

    Node<Character> root;
    root = new Node<>('A');
    root.left = new Node<>('B');
    root.left.left = new Node<>('C');
    root.left.left.left = new Node<>('D');
    root.right = new Node<>('P');
    root.right.right = new Node<>('Q');

The difference in the output from the correct result is small for 4 levels, but it gets much worse if you stack more nodes to the left and to the right branches.

Alternative implementation

Here's a recursive implementation that works correctly, and it also happens to be a lot simpler:

<T> void printLevelOrder(Node<T> root) {
    if (root != null) {
        printLevelOrder(Arrays.asList(root));
    }
}

<T> void printLevelOrder(List<Node<T>> level) {
    List<Node<T>> nextLevel = new LinkedList<>();
    for (Node<T> node : level) {
        System.out.println(node.data);
        if (node.left != null) {
            nextLevel.add(node.left);
        }
        if (node.right != null) {
            nextLevel.add(node.right);
        }
    }
    if (!nextLevel.isEmpty()) {
        printLevelOrder(nextLevel);
    }
}

Other coding style issues

Don't check boolean expressions like this:

while(stack.isEmpty() == false) {

"Empty equals false" is really a confusing way to say "not empty"

while (!stack.isEmpty()) {

Starting from Java 7, you don't need to specify type parameters like this:

Stack<Node> stack = new Stack<Node>();

You can use the diamond <> operator and the compiler can figure out what to do:

Stack<Node> stack = new Stack<>();
share|improve this answer
1  
Yep, mine is not working as it keeps going 'left' after level 3, then to 'right'. Thanks! –  Tech Junkie Jun 7 at 16:55
    
I could re-work your implementation for zigzag level order traversal too! –  Tech Junkie Jun 7 at 17:27
up vote 4 down vote

A few things that catch my eye, just skimming over your code:

  1. Unconventional method names:

    Java method names are supposed to be named strictly in camelCase. You're using some bastardized camel-snake-pascal-case which is something I'd expect when mixing together PHP, Python and C++... ~shivers

  2. Use of outdated API:

    Stack is a class in Java retroactively added to the Collections API, but it should've been officially deprecated since Java 1.5. It's been officially replaced by Deque, which is an interface that supports all stack-operations, see also Stack's javadoc:

    A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations

  3. Returning a Collection from a method which begins with print

    A method name should not lie. For a method named print... I'd expect to give something to be printed and some output channel (e.g. BufferedOutputWriter) with no return value. Instead you should name it something like traverseLevelOrder.

  4. Overcomplicated helper method:

    For a recursive traversal it's definitely not necessary to have a method that takes two nodes. Instead of relying on the caller to maintain the Stack you have, you may want to give the Stack (or better the Deque) into the recursive traversal for a level-order traversal. Also it's a significant difference whether you only want to traverse the nodes or also keep the traversal results in memory...

  5. General recursive approach:

    It might be a better option to actually do the level-order traversal with an "iterative" approach, by maintaining the nodes you still have to traverse in a queue that builds up by level and just process them back again. Following code should give you an idea:

    void traverse(Node node) {
    Queue<Node> traversalQueue = new LinkedList<>();
    traversalQueue.add(node);
    while (!traversalQueue.isEmpty()) {
        // add nodes to queue by level
        // and pop the current:
        traversalQueue.add(node.left); // null-checks omitted
        traversalQueue.add(node.right);
        // use node.data
    }
}
share|improve this answer
up vote 3 down vote

This is… interesting code. Breadth-first traversals are normally done using a queue. It seems that you are aware of that, since you wrote Queue<Node> queue = new LinkedList<Node>(); queue.add(root2); — but then you never used queue again after that. Instead, you use a lot of Stack<Node> data structures, with items stored in reverse order so that when you pop() them in this loop…

while(stack.isEmpty() == false) {
    Node node = stack.pop();
    System.out.println(node.data);
}

the nodes will be "de-queued" in the desired order.

Furthermore, those aren't really stacks. Stacks traditionally support operations push, pop, and peek, with bookkeeping operations size and isEmpty. When you call stack.addAll(…), that's taking advantage of Java's poorly designed java.util.Stack implementation which mistakenly inherits from java.util.Vector. The .addAll() method shouldn't really be available in a proper stack.

I recommend starting over, using no stacks and only the queue.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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