CODEWITHSUNDEEP
javaalgorithmtreequeuetraversal
Mona Jalal
Mona Jalal

Reputation: 38145

Wrong LevelOrder Traversal

How can I fix this LevelOrder traversal?

public static void LevelOrder(TreeNode root){
        Queue <TreeNode> q = new LinkedList <>();
        TreeNode tmp=root;
        q.add(tmp);
        while (!q.isEmpty()) {
            System.out.print(q.remove().data + " ");
            if (tmp.left!=null) {
                q.add(tmp.left);
            }
            if (tmp.left!=null) {
                q.add(tmp.right);
            }
                tmp = q.peek();
        }

    }

Upvotes: 1

Views: 52

Answers (1)

janos
janos

Reputation: 124648

Don't just remove() from the queue without storing. Save it in a variable, as you need it to check left and right. You also didn't check if root is null. A possible fix to both issues:

public static void LevelOrder(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode tmp = q.remove();
        if (tmp == null) {
            continue;
        }
        System.out.print(tmp.data + " ");
        q.add(tmp.left);
        q.add(tmp.right);
    }
}

Instead of remove(), I suggest using poll(). The difference is that remove() will throw an exception if the queue is empty. But thanks to the loop condition we know that cannot happen. For more details on the various methods of LinkedList see the JavaDoc.

Upvotes: 1

Related Questions