Symmetric Binary Tree Editorial

Practice Problem Link: Symmetric Binary Tree

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

A binary tree is considered symmetric if it is a mirror image of itself, i.e, it is symmetric around its root node.

Given the root node of a binary tree, determine whether it's symmetric.

Approach (BFS)

For a symmetric binary tree, the elements at each level will be palindromic. We can use level order traversal using queue and check every level in the tree if it is palindromic or not. To do this:

• First, insert the root node twice in the queue.
• Now while the queue is not empty remove the first two elements as the leftChild and rightChild respectively.
• Compare the leftChild and the rightChild. If they are equal then insert the left node of leftChild and right node of rightChild in the queue followed by the right node of leftChild and left node of rightChild.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
bool isSymmetric(Node* root) {
	queue<Node*> treeNodes;
	treeNodes.push(root);
	treeNodes.push(root);
	while (!treeNodes.empty()) {
		Node* leftChild = treeNodes.front();
		treeNodes.pop();
		Node* rightChild = treeNodes.front();
		treeNodes.pop();
		if (leftChild->data != rightChild->data) {
			return false;
		}
		if(leftChild->left != NULL && rightChild->right != NULL) {
			treeNodes.push(leftChild->left);
			treeNodes.push(rightChild->right);
		}
		else if(leftChild->left != NULL || rightChild->right != NULL) {
			return false;		
		}
		if(leftChild->right != NULL && rightChild->left != NULL) {
			treeNodes.push(leftChild->right);
			treeNodes.push(rightChild->left);
		}
		else if(leftChild->right != NULL || rightChild->left != NULL) {
			return false;
		}
	}
	return true;
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	boolean isSymmetric(Node root) {
	    Queue<Node> treeNodes = new LinkedList<Node> ();
		treeNodes.add(root);
		treeNodes.add(root);
		while (!treeNodes.isEmpty()) {
			Node leftChild = treeNodes.peek();
			treeNodes.poll();
			Node rightChild = treeNodes.peek();
			treeNodes.poll();
			if (leftChild.data != rightChild.data) {
				return false;
			}
			if(leftChild.left != null && rightChild.right != null) {
				treeNodes.add(leftChild.left);
				treeNodes.add(rightChild.right);
			}
			else if(leftChild.left != null || rightChild.right != null) {
				return false;		
			}
			if(leftChild.right != null && rightChild.left != null) {
				treeNodes.add(leftChild.right);
				treeNodes.add(rightChild.left);
			}
			else if(leftChild.right != null || rightChild.left != null) {
				return false;
			}
		}
		return true;
	}
}

Approach (DFS)

The idea is to check two trees recursively if the left subtree of the first tree is the mirror image of the right subtree of the second tree and the right subtree of the first tree is the mirror image of the left subtree of the second tree for every node in the tree.

Initially, both the trees will be the same (i.e. the given tree).

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
bool isMirrorImage(Node* firstRoot, Node* secondRoot) {
	if(firstRoot == NULL && secondRoot == NULL) {
		return true;
	}
	if(firstRoot == NULL || secondRoot == NULL) {
		return false;
	}
	if(firstRoot->data != secondRoot->data) {
		return false;
	}
	if(isMirrorImage(firstRoot->left, secondRoot->right) == false || isMirrorImage(firstRoot->right, secondRoot->left) == false) {
		return false;
	}
	return true;
}
bool isSymmetric(Node* root) {
	return isMirrorImage(root, root);
}

Java

class Solution {
	/* This is the Node class definition
	
	class Node {
		public Node left;
		public Node right;
		public int data;

		public Node(int data) {
			this.data = data;
		}
	}
	*/
	boolean isMirrorImage(Node firstRoot, Node secondRoot) {
		if(firstRoot == null && secondRoot == null) {
			return true;
		}
		if(firstRoot == null || secondRoot == null) {
			return false;
		}
		if(firstRoot.data != secondRoot.data) {
			return false;
		}
		if(isMirrorImage(firstRoot.left, secondRoot.right) == false || isMirrorImage(firstRoot.right, secondRoot.left) == false) {
			return false;
		}
		return true;
	}
	boolean isSymmetric(Node root) {
	    return isMirrorImage(root, root);
	}
}