Problem: Given the root of Binary Tree you need to check whether the tree is symmetric or not.
A tree is said to be symmetric if it is mirror of itself if divided from center.
Example 1:
Input: root = [1, 2, 2, 3, null, null, 3]
Output: true : Tree is Symmetric.
Output: true : Tree is Symmetric.
Example 2:
Input: p = [1, 2, 2, 3, 4, 4, 10]
Output: false
Output: false
Approach:
The problem can be solved using Recursion. We simply need to check the value of nodes in the left sub tree with the nodes value in right sub tree. If we encounter any two nodes which doesn't have any same value it means the tree is not symmetric at all.
Code Implementation:
public class SymmetricTree {
public static Node root;
public static class Node {
int val;
Node left, right;
Node(int data) {
val = data;
left = right = null;
}
}
public static void main(String[] args) {
root = new Node(1);
root.left = new Node(2);
root.right = new Node(2);
root.left.left = new Node(3);
root.left.right = new Node(4);
root.right.left = new Node(4);
root.right.right = new Node(10);
/*
* root is same so checking on left subtree and right subtree
*/
boolean result = isSymmetric(root.left, root.right);
if (result == true) {
System.out.println(result + " : Tree is Symmetric.");
} else {
System.out.println(result + " : Tree is not symmetric.");
}
}
private static boolean isSymmetric(Node p, Node q) {
// if p is null and q is null return true
if (p == null && q == null)
return true;
// if either of p, q is null it means tree is not symmetric
if (p == null || q == null)
return false;
/*
* checking for the values of p and q and calling isSymmetric() for left of p,
* right of q and similarly calling isSymmetric() for right of p, left of q
*/
return (p.val == q.val) && isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);
}
}
Output:
false : Tree is not symmetric.
Complexity Analysis:
Time Complexity: O(n), where n is the number of nodes in tree.
Space Complexity: O(h), where h is height of tree.