Repository: TheAlgorithms/Java
Pull request #3472 (2022-10-09 19:59:13)

Fixes: 3471: Symmetric tree
### **Describe your change:**

- [x] Add an algorithm?
- [ ] Fix a bug or typo in an existing algorithm?
- [ ] Documentation change?

#### References

<!-- Add any reference to previous pull-request or issue -->

https://github.com/TheAlgorithms/Java/issues/3471

<!-- Remove items that do not apply. 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.
- [x] I know that pull requests will not be merged if they fail the automated tests.
- [x] This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
- [x] All new Java files are placed inside an existing directory.
- [ ] All filenames are in all uppercase characters with no spaces or dashes.
- [x] All functions and variable names follow Java naming conventions.
- [ ] All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
- [ ] If this pull request resolves one or more open issues then the commit message contains `Fixes: #{$ISSUE_NO}`.



Patch:
diff --git a/src/main/java/com/thealgorithms/datastructures/trees/CheckTreeIsSymmetric.java b/src/main/java/com/thealgorithms/datastructures/trees/CheckTreeIsSymmetric.java
new file mode 100644
index 00000000..713dc083
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/trees/CheckTreeIsSymmetric.java
@@ -0,0 +1,53 @@
+package com.thealgorithms.datastructures.trees;
+
+import com.thealgorithms.datastructures.trees.BinaryTree.Node;
+
+/**
+ * Check if a binary tree is symmetric or not.
+ * A binary tree is a symmetric tree if the left and right subtree of root are mirror image.
+ * Below is a symmetric tree
+ *                               1
+ *                   /                         \
+ *                2                           2
+ *         /                \             /             \
+ *      3                    4         4                3
+ *
+ * Below is not symmetric because values is different in last level
+ *                               1
+ *                   /                         \
+ *                 2                           2
+ *         /                \             /             \
+ *      3                    5         4                3
+ * <p>
+ * Approach:
+ * Recursively check for left and right subtree of root
+ * 1. left subtrees root's values should be equal right subtree's root value
+ * 2. recursively check with left subtrees' left child VS right subtree's right child AND
+ * left subtree's right child VS right subtree left child
+ * Complexity
+ * 1. Time: O(n)
+ * 2. Space: O(lg(n)) for height of tree
+ *
+ * @author kumanoit on 10/10/22 IST 12:52 AM
+ */
+public class CheckTreeIsSymmetric {
+
+    public static boolean isSymmetric(Node root) {
+        if (root == null) {
+            return true;
+        }
+        return isSymmetric(root.left, root.right);
+    }
+
+    private static boolean isSymmetric(Node leftSubtreeRoot, Node rightSubtreRoot) {
+        if (leftSubtreeRoot == null && rightSubtreRoot == null) {
+            return true;
+        }
+
+        if (leftSubtreeRoot == null || rightSubtreRoot == null || leftSubtreeRoot.data != rightSubtreRoot.data) {
+            return false;
+        }
+
+        return isSymmetric(leftSubtreeRoot.right, rightSubtreRoot.left) && isSymmetric(leftSubtreeRoot.left, rightSubtreRoot.right);
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/trees/CheckTreeIsSymmetricTest.java b/src/test/java/com/thealgorithms/datastructures/trees/CheckTreeIsSymmetricTest.java
new file mode 100644
index 00000000..932d5b88
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/trees/CheckTreeIsSymmetricTest.java
@@ -0,0 +1,36 @@
+package com.thealgorithms.datastructures.trees;
+
+import org.junit.jupiter.api.Test;
+
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertTrue;
+
+/**
+ * @author kumanoit on 10/10/22 IST 1:02 AM
+ */
+public class CheckTreeIsSymmetricTest {
+
+    @Test
+    public void testRootNull() {
+        assertTrue(CheckTreeIsSymmetric.isSymmetric(null));
+    }
+
+    @Test
+    public void testSingleNodeTree() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[]{100});
+        assertTrue(CheckTreeIsSymmetric.isSymmetric(root));
+    }
+
+    @Test
+    public void testSymmetricTree() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[]{1,2,2,3,4,4,3});
+        assertTrue(CheckTreeIsSymmetric.isSymmetric(root));
+    }
+
+    @Test
+    public void testNonSymmetricTree() {
+        final BinaryTree.Node root = TreeTestUtils.createTree(new Integer[]{1,2,2,3,5,4,3});
+        assertFalse(CheckTreeIsSymmetric.isSymmetric(root));
+    }
+
+}