Repository: TheAlgorithms/Java
Pull request #3869 (2023-02-08 20:09:55)

Level order traversal refactoring, added unit test
<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.


albina-astr: @siriak Hi! I've fixed this PR.

Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/trees/LevelOrderTraversal.java b/src/main/java/com/thealgorithms/datastructures/trees/LevelOrderTraversal.java
index 64ce1f4b..4b86d644 100644
--- a/src/main/java/com/thealgorithms/datastructures/trees/LevelOrderTraversal.java
+++ b/src/main/java/com/thealgorithms/datastructures/trees/LevelOrderTraversal.java
@@ -1,58 +1,38 @@
 package com.thealgorithms.datastructures.trees;
 
-public class LevelOrderTraversal {
-
-    class Node {
-
-        int data;
-        Node left, right;
-
-        public Node(int item) {
-            data = item;
-            left = right = null;
-        }
-    }
+import java.util.ArrayList;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Queue;
 
-    // Root of the Binary Tree
-    Node root;
-
-    public LevelOrderTraversal(Node root) {
-        this.root = root;
-    }
-
-    /* function to print level order traversal of tree*/
-    void printLevelOrder() {
-        int h = height(root);
-        int i;
-        for (i = 1; i <= h; i++) {
-            printGivenLevel(root, i);
-        }
-    }
+public class LevelOrderTraversal {
 
-    /* Compute the "height" of a tree -- the number of
-  nodes along the longest path from the root node
-  down to the farthest leaf node.*/
-    int height(Node root) {
+    static List<List<Integer>> traverse(BinaryTree.Node root) {
         if (root == null) {
-            return 0;
-        } else {
-            /**
-             * Return the height of larger subtree
-             */
-            return Math.max(height(root.left), height(root.right)) + 1;
+            return List.of();
         }
-    }
 
-    /* Print nodes at the given level */
-    void printGivenLevel(Node root, int level) {
-        if (root == null) {
-            return;
-        }
-        if (level == 1) {
-            System.out.print(root.data + " ");
-        } else if (level > 1) {
-            printGivenLevel(root.left, level - 1);
-            printGivenLevel(root.right, level - 1);
+        List<List<Integer>> result = new ArrayList<>();
+
+        Queue<BinaryTree.Node> q = new LinkedList<>();
+        q.add(root);
+        while (!q.isEmpty()) {
+            int nodesOnLevel = q.size();
+            List<Integer> level = new LinkedList<>();
+            for (int i = 0; i < nodesOnLevel; i++) {
+                BinaryTree.Node tempNode = q.poll();
+                level.add(tempNode.data);
+
+                if (tempNode.left != null) {
+                    q.add(tempNode.left);
+                }
+
+                if (tempNode.right != null) {
+                    q.add(tempNode.right);
+                }
+            }
+            result.add(level);
         }
+        return result;
     }
 }
diff --git a/src/main/java/com/thealgorithms/datastructures/trees/LevelOrderTraversalHelper.java b/src/main/java/com/thealgorithms/datastructures/trees/LevelOrderTraversalHelper.java
new file mode 100644
index 00000000..8fa3dc72
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/trees/LevelOrderTraversalHelper.java
@@ -0,0 +1,43 @@
+package com.thealgorithms.datastructures.trees;
+
+public class LevelOrderTraversalHelper {
+    /* function to print level order traversal of tree*/
+    public static void printLevelOrder(BinaryTree.Node root) {
+        if (root == null) {
+            System.out.println("Root node must not be null! Exiting.");
+            return;
+        }
+
+        int h = height(root);
+        int i;
+        for (i = 1; i <= h; i++) {
+            printGivenLevel(root, i);
+        }
+    }
+
+    /* Compute the "height" of a tree -- the number of
+  nodes along the longest path from the root node
+  down to the farthest leaf node.*/
+    private static int height(BinaryTree.Node root) {
+        if (root == null) {
+            return 0;
+        } else {
+            //return the height of larger subtree
+            return Math.max(height(root.left), height(root.right)) + 1;
+        }
+    }
+
+    /* Print nodes at the given level */
+    public static void printGivenLevel(BinaryTree.Node root, int level) {
+        if (root == null) {
+            System.out.println("Root node must not be null! Exiting.");
+            return;
+        }
+        if (level == 1) {
+            System.out.print(root.data + " ");
+        } else if (level > 1) {
+            printGivenLevel(root.left, level - 1);
+            printGivenLevel(root.right, level - 1);
+        }
+    }
+}
diff --git a/src/main/java/com/thealgorithms/datastructures/trees/LevelOrderTraversalQueue.java b/src/main/java/com/thealgorithms/datastructures/trees/LevelOrderTraversalQueue.java
deleted file mode 100644
index 65a0d6e1..00000000
--- a/src/main/java/com/thealgorithms/datastructures/trees/LevelOrderTraversalQueue.java
+++ /dev/null
@@ -1,45 +0,0 @@
-package com.thealgorithms.datastructures.trees;
-
-import java.util.LinkedList;
-import java.util.Queue;
-
-/* Class to print Level Order Traversal */
-public class LevelOrderTraversalQueue {
-
-    /* Class to represent Tree node */
-    class Node {
-
-        int data;
-        Node left, right;
-
-        public Node(int item) {
-            data = item;
-            left = null;
-            right = null;
-        }
-    }
-
-    /* Given a binary tree. Print its nodes in level order
-  using array for implementing queue  */
-    void printLevelOrder(Node root) {
-        Queue<Node> queue = new LinkedList<Node>();
-        queue.add(root);
-        while (!queue.isEmpty()) {
-            /* poll() removes the present head.
-      For more information on poll() visit
-      http://www.tutorialspoint.com/java/util/linkedlist_poll.htm */
-            Node tempNode = queue.poll();
-            System.out.print(tempNode.data + " ");
-
-            /*Enqueue left child */
-            if (tempNode.left != null) {
-                queue.add(tempNode.left);
-            }
-
-            /*Enqueue right child */
-            if (tempNode.right != null) {
-                queue.add(tempNode.right);
-            }
-        }
-    }
-}
diff --git a/src/main/java/com/thealgorithms/datastructures/trees/ZigzagTraversal.java b/src/main/java/com/thealgorithms/datastructures/trees/ZigzagTraversal.java
index 9026fdfa..7aafcdf8 100644
--- a/src/main/java/com/thealgorithms/datastructures/trees/ZigzagTraversal.java
+++ b/src/main/java/com/thealgorithms/datastructures/trees/ZigzagTraversal.java
@@ -32,7 +32,7 @@ import java.util.*;
 public class ZigzagTraversal {
     public static List<List<Integer>> traverse(BinaryTree.Node root) {
         if (root == null) {
-            return new ArrayList<>();
+            return List.of();
         }
 
         List<List<Integer>> result = new ArrayList<>();


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/trees/LevelOrderTraversalTest.java b/src/test/java/com/thealgorithms/datastructures/trees/LevelOrderTraversalTest.java
new file mode 100644
index 00000000..8b0a6b65
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/trees/LevelOrderTraversalTest.java
@@ -0,0 +1,54 @@
+package com.thealgorithms.datastructures.trees;
+
+import org.junit.jupiter.api.Test;
+
+import java.util.Collections;
+import java.util.List;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+/**
+ * @author Albina Gimaletdinova on 08/02/2023
+ */
+public class LevelOrderTraversalTest {
+    @Test
+    public void testRootNull() {
+        assertEquals(Collections.emptyList(), LevelOrderTraversal.traverse(null));
+    }
+
+    @Test
+    public void testSingleNodeTree() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[]{50});
+        assertEquals(List.of(List.of(50)), LevelOrderTraversal.traverse(root));
+    }
+
+    /*
+         1
+        / \
+       2   3
+      /\   /\
+     4  5 6  7
+    */
+    @Test
+    public void testLevelOrderTraversalCompleteTree() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[]{1, 2, 3, 4, 5, 6, 7});
+        assertEquals(List.of(List.of(1), List.of(2, 3), List.of(4, 5, 6, 7)), LevelOrderTraversal.traverse(root));
+    }
+
+    /*
+         1
+        / \
+       2   3
+      /\   /\
+     4  5 6  7
+        /  \
+       8    9
+    */
+    @Test
+    public void testLevelOrderTraversalDifferentHeight() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(
+                new Integer[]{1, 2, 3, 4, 5, 6, 7, null, null, 8, null, null, 9});
+        assertEquals(List.of(List.of(1), List.of(2, 3), List.of(4, 5, 6, 7), List.of(8, 9)),
+                LevelOrderTraversal.traverse(root));
+    }
+}
diff --git a/src/test/java/com/thealgorithms/datastructures/trees/VerticalOrderTraversalTest.java b/src/test/java/com/thealgorithms/datastructures/trees/VerticalOrderTraversalTest.java
index 42875e4f..74b036d1 100644
--- a/src/test/java/com/thealgorithms/datastructures/trees/VerticalOrderTraversalTest.java
+++ b/src/test/java/com/thealgorithms/datastructures/trees/VerticalOrderTraversalTest.java
@@ -40,7 +40,7 @@ public class VerticalOrderTraversalTest {
         / \
        2   3
       /\   /\
-     4   56  7
+     4  5 6  7
         /  \
        8    9
     */
diff --git a/src/test/java/com/thealgorithms/datastructures/trees/ZigzagTraversalTest.java b/src/test/java/com/thealgorithms/datastructures/trees/ZigzagTraversalTest.java
index 11af07c5..6b89fcff 100644
--- a/src/test/java/com/thealgorithms/datastructures/trees/ZigzagTraversalTest.java
+++ b/src/test/java/com/thealgorithms/datastructures/trees/ZigzagTraversalTest.java
@@ -22,9 +22,33 @@ public class ZigzagTraversalTest {
         assertEquals(List.of(List.of(50)), ZigzagTraversal.traverse(root));
     }
 
+    /*
+         1
+        / \
+       2   3
+      /\   /\
+     4  5 6  7
+    */
     @Test
-    public void testZigzagTraversal() {
-        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[]{7, 6, 14, 2, 80, 100});
-        assertEquals(List.of(List.of(7), List.of(14, 6), List.of(2, 80, 100)), ZigzagTraversal.traverse(root));
+    public void testZigzagTraversalCompleteTree() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[]{1, 2, 3, 4, 5, 6, 7});
+        assertEquals(List.of(List.of(1), List.of(3, 2), List.of(4, 5, 6, 7)), ZigzagTraversal.traverse(root));
+    }
+
+    /*
+         1
+        / \
+       2   3
+      /\   /\
+     4  5 6  7
+        /  \
+       8    9
+    */
+    @Test
+    public void testZigzagTraversalDifferentHeight() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(
+                new Integer[]{1, 2, 3, 4, 5, 6, 7, null, null, 8, null, null, 9});
+        assertEquals(List.of(List.of(1), List.of(3, 2), List.of(4, 5, 6, 7), List.of(9, 8)),
+                ZigzagTraversal.traverse(root));
     }
 }