Repository: TheAlgorithms/Java
Pull request #5639 (2024-10-08 09:15:57)

Add boundary traversal of binary tree
This PR implements the boundary traversal algorithm for a binary tree as requested in the related issue. The boundary traversal is performed in three parts:

Left Boundary: Traverses the left boundary of the tree, excluding leaf nodes.
Leaf Nodes: Collects all leaf nodes from left to right.
Right Boundary: Traverses the right boundary of the tree, excluding leaf nodes, and adds the nodes in reverse order to ensure correct boundary order.
Both time complexity and space complexity of this implementation are O(n), where n is the number of nodes in the binary tree.

The boundary traversal is performed both iteratively and recursively, and edge cases such as single-node trees and trees without left or right subtrees are handled appropriately.
All methods in the test class passed the test.


codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5639?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 58.38%. Comparing base [(`0d68b65`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/0d68b655d21d7f8d6a996f64c2e6f5d33eba95b5?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`427adbd`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/427adbd874ca730f8170aa5e70e9e8250413af7a?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5639      +/-   ##
============================================
+ Coverage     58.20%   58.38%   +0.17%     
- Complexity     3693     3731      +38     
============================================
  Files           549      550       +1     
  Lines         15850    15916      +66     
  Branches       3015     3040      +25     
============================================
+ Hits           9226     9292      +66     
  Misses         6232     6232              
  Partials        392      392              
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5639?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/trees/BoundaryTraversal.java b/src/main/java/com/thealgorithms/datastructures/trees/BoundaryTraversal.java
new file mode 100644
index 00000000..9a79902c
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/trees/BoundaryTraversal.java
@@ -0,0 +1,168 @@
+package com.thealgorithms.datastructures.trees;
+
+import java.util.ArrayList;
+import java.util.Deque;
+import java.util.LinkedList;
+import java.util.List;
+
+/**
+ * BoundaryTraversal
+ * <p>
+ * Start with the Root:
+ * Add the root node to the boundary list.
+ * Traverse the Left Boundary (Excluding Leaf Nodes):
+ * Move down the left side of the tree, adding each non-leaf node to the boundary list.
+ * If a node has a left child, go left; otherwise, go right.
+ * Visit All Leaf Nodes:
+ * Traverse the tree and add all leaf nodes to the boundary list, from left to right.
+ * Traverse the Right Boundary (Excluding Leaf Nodes) in Reverse Order:
+ * Move up the right side of the tree, adding each non-leaf node to a temporary list.
+ * If a node has a right child, go right; otherwise, go left.
+ * Reverse the temporary list and add it to the boundary list.
+ * Combine and Output:
+ * The final boundary list contains the root, left boundary, leaf nodes, and reversed right boundary in that order.
+ */
+public final class BoundaryTraversal {
+    private BoundaryTraversal() {
+    }
+
+    // Main function for boundary traversal, returns a list of boundary nodes in order
+    public static List<Integer> boundaryTraversal(BinaryTree.Node root) {
+        List<Integer> result = new ArrayList<>();
+        if (root == null) {
+            return result;
+        }
+
+        // Add root node if it's not a leaf node
+        if (!isLeaf(root)) {
+            result.add(root.data);
+        }
+
+        // Add left boundary
+        addLeftBoundary(root, result);
+
+        // Add leaf nodes
+        addLeaves(root, result);
+
+        // Add right boundary
+        addRightBoundary(root, result);
+
+        return result;
+    }
+
+    // Adds the left boundary, including nodes that have no left child but have a right child
+    private static void addLeftBoundary(BinaryTree.Node node, List<Integer> result) {
+        BinaryTree.Node cur = node.left;
+
+        // If there is no left child but there is a right child, treat the right child as part of the left boundary
+        if (cur == null && node.right != null) {
+            cur = node.right;
+        }
+
+        while (cur != null) {
+            if (!isLeaf(cur)) {
+                result.add(cur.data); // Add non-leaf nodes to result
+            }
+            if (cur.left != null) {
+                cur = cur.left; // Move to the left child
+            } else if (cur.right != null) {
+                cur = cur.right; // If left child is null, move to the right child
+            } else {
+                break; // Stop if there are no children
+            }
+        }
+    }
+
+    // Adds leaf nodes (nodes without children)
+    private static void addLeaves(BinaryTree.Node node, List<Integer> result) {
+        if (node == null) {
+            return;
+        }
+        if (isLeaf(node)) {
+            result.add(node.data); // Add leaf node
+        } else {
+            addLeaves(node.left, result); // Recur for left subtree
+            addLeaves(node.right, result); // Recur for right subtree
+        }
+    }
+
+    // Adds the right boundary, excluding leaf nodes
+    private static void addRightBoundary(BinaryTree.Node node, List<Integer> result) {
+        BinaryTree.Node cur = node.right;
+        List<Integer> temp = new ArrayList<>();
+
+        // If no right boundary is present and there is no left subtree, skip
+        if (cur != null && node.left == null) {
+            return;
+        }
+        while (cur != null) {
+            if (!isLeaf(cur)) {
+                temp.add(cur.data); // Store non-leaf nodes temporarily
+            }
+            if (cur.right != null) {
+                cur = cur.right; // Move to the right child
+            } else if (cur.left != null) {
+                cur = cur.left; // If right child is null, move to the left child
+            } else {
+                break; // Stop if there are no children
+            }
+        }
+
+        // Add the right boundary nodes in reverse order
+        for (int i = temp.size() - 1; i >= 0; i--) {
+            result.add(temp.get(i));
+        }
+    }
+
+    // Checks if a node is a leaf node
+    private static boolean isLeaf(BinaryTree.Node node) {
+        return node.left == null && node.right == null;
+    }
+
+    // Iterative boundary traversal
+    public static List<Integer> iterativeBoundaryTraversal(BinaryTree.Node root) {
+        List<Integer> result = new ArrayList<>();
+        if (root == null) {
+            return result;
+        }
+
+        // Add root node if it's not a leaf node
+        if (!isLeaf(root)) {
+            result.add(root.data);
+        }
+
+        // Handle the left boundary
+        BinaryTree.Node cur = root.left;
+        if (cur == null && root.right != null) {
+            cur = root.right;
+        }
+        while (cur != null) {
+            if (!isLeaf(cur)) {
+                result.add(cur.data); // Add non-leaf nodes to result
+            }
+            cur = (cur.left != null) ? cur.left : cur.right; // Prioritize left child, move to right if left is null
+        }
+
+        // Add leaf nodes
+        addLeaves(root, result);
+
+        // Handle the right boundary using a stack (reverse order)
+        cur = root.right;
+        Deque<Integer> stack = new LinkedList<>();
+        if (cur != null && root.left == null) {
+            return result;
+        }
+        while (cur != null) {
+            if (!isLeaf(cur)) {
+                stack.push(cur.data); // Temporarily store right boundary nodes in a stack
+            }
+            cur = (cur.right != null) ? cur.right : cur.left; // Prioritize right child, move to left if right is null
+        }
+
+        // Add the right boundary nodes from the stack to maintain the correct order
+        while (!stack.isEmpty()) {
+            result.add(stack.pop());
+        }
+        return result;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/trees/BoundaryTraversalTest.java b/src/test/java/com/thealgorithms/datastructures/trees/BoundaryTraversalTest.java
new file mode 100644
index 00000000..515dac88
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/trees/BoundaryTraversalTest.java
@@ -0,0 +1,108 @@
+package com.thealgorithms.datastructures.trees;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.Collections;
+import java.util.List;
+import org.junit.jupiter.api.Test;
+
+/**
+ *
+ */
+public class BoundaryTraversalTest {
+
+    @Test
+    public void testNullRoot() {
+        assertEquals(Collections.emptyList(), BoundaryTraversal.boundaryTraversal(null));
+        assertEquals(Collections.emptyList(), BoundaryTraversal.iterativeBoundaryTraversal(null));
+    }
+
+    @Test
+    public void testSingleNodeTree() {
+        final BinaryTree.Node root = new BinaryTree.Node(1);
+
+        List<Integer> expected = List.of(1);
+
+        assertEquals(expected, BoundaryTraversal.boundaryTraversal(root));
+        assertEquals(expected, BoundaryTraversal.iterativeBoundaryTraversal(root));
+    }
+
+    /*
+        1
+       / \
+      2   3
+     / \ / \
+    4  5 6  7
+
+    */
+    @Test
+    public void testCompleteBinaryTree() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {1, 2, 3, 4, 5, 6, 7});
+
+        List<Integer> expected = List.of(1, 2, 4, 5, 6, 7, 3);
+
+        assertEquals(expected, BoundaryTraversal.boundaryTraversal(root));
+        assertEquals(expected, BoundaryTraversal.iterativeBoundaryTraversal(root));
+    }
+
+    /*
+        1
+       / \
+      2   7
+     /     \
+    3       8
+     \     /
+      4   9
+         / \
+        5   6
+           / \
+         10  11
+    */
+    @Test
+    public void testBoundaryTraversal() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {1, 2, 7, 3, null, null, 8, null, 4, 9, null, 5, 6, 10, 11});
+
+        List<Integer> expected = List.of(1, 2, 3, 4, 5, 6, 10, 11, 9, 8, 7);
+
+        assertEquals(expected, BoundaryTraversal.boundaryTraversal(root));
+        assertEquals(expected, BoundaryTraversal.iterativeBoundaryTraversal(root));
+    }
+
+    /*
+          1
+         /
+        2
+       /
+      3
+     /
+    4
+    */
+    @Test
+    public void testLeftSkewedTree() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {1, 2, null, 3, null, 4, null});
+
+        List<Integer> expected = List.of(1, 2, 3, 4);
+
+        assertEquals(expected, BoundaryTraversal.boundaryTraversal(root));
+        assertEquals(expected, BoundaryTraversal.iterativeBoundaryTraversal(root));
+    }
+
+    /*
+              5
+               \
+                6
+                 \
+                  7
+                   \
+                    8
+    */
+    @Test
+    public void testRightSkewedTree() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[] {5, null, 6, null, 7, null, 8});
+
+        List<Integer> expected = List.of(5, 6, 7, 8);
+
+        assertEquals(expected, BoundaryTraversal.boundaryTraversal(root));
+        assertEquals(expected, BoundaryTraversal.iterativeBoundaryTraversal(root));
+    }
+}