Binary Tree: Check if a binary tree is symmetric or mirror of itself
Property of Symmetric Binary Tree
The Left Subtree and the Right Subtree of a given node in a Symmetric Binary Tree are mirror images of each other
How to check if a tree is Symmetric or not?
We check if a tree is symmetric or not by comparing the left subtree of root with the right subtree and checking if all the nodes are mirror of themselves
Comparing if nodes are mirror
- Traverse the tree in Inorder[left root right] and simultaneously traverse the tree in mirror of Inorder[right root left], taking one step at a time
- Check if the current node from Inorder has same data as the node from mirror Inorder
- If same data: check it's children nodes
- Else: return false
- If all nodes are visited return true
To solve this problem we have to traverse the tree and tree traversal can be done in two ways: Iterative and Recursive.
In this article we will be going through the Recursive approach
Diagram
Example 1:
Example 2:
Complexity:
As we are simply traversing the tree the Time Complexity and Space Complexity will be the same as that of traversing a Tree
Time Complexity : O(n) , where n is the number of nodes in binary tree
Space Complexity: O(Height of Tree)
The Time Complexity will be O(N) as we have to check each node at least once and the space complexity will be
O(Height of Tree) which is O(logN) for a perfect binary tree, the Space Complexity is because
of the stack memory consumed by the recursive calls
Java Code
class BinaryTreeCheckSymmetry{
static class Node {
// Node class for Binary Search Tree
int data;
Node left, right;
// Constructor to set the value of the node
Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
// Function to check if a given tree is symmetric or not
static boolean isSymmetric(Node root) {
// Edge Case: A empty tree is said to be symmetric
if (root == null) {
return true;
}
return isMirror(root, root);
}
static boolean isMirror(Node node1, Node node2) {
// Base Case: if both the subtree roots are null
if (node1 == null && node2 == null) {
return true;
}
// We Recursively traverse the tree for both the roots
// Check if both the roots value are same or not
if (node1 != null && node2 != null && node1.data == node2.data) {
// We have to check for both the sides,
// for node1 of left with node2 right and node1 of right with the node2 of
// left
return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
}
// If above cases are not true, then we return false
return false;
}
public static void main(String[] args) {
// Example 1:
Node tree1 = new Node(1);
tree1.left = new Node(2);
tree1.right = new Node(2);
tree1.left.left = new Node(3);
tree1.left.right = new Node(4);
tree1.right.left = new Node(4);
tree1.right.right = new Node(3);
if (isSymmetric(tree1)) {
System.out.println("The Example 1 is Symmetric");
} else {
System.out.println("The Example 1 is Not Symmetric");
}
// Example 2:
Node tree2 = new Node(1);
tree2.left = new Node(2);
tree2.right = new Node(2);
tree2.left.right = new Node(3);
tree2.right.right = new Node(3);
if (isSymmetric(tree2)) {
System.out.println("The Example 2 is Symmetric");
} else {
System.out.println("The Example 2 is Not Symmetric");
}
}
}
Output
The Example 1 is Symmetric
The Example 2 is Not Symmetric