Check if binary tree is symmetrical

In this article, we will discuss the algorithms to find out whether the given binary tree is symmetrical or non-symmetrical.

What we'll see,

• A binary tree
• A symmetrical binary tree
• The Recursive Approach
  • Time complexity
  • Space complexity
• The Iterative Approach
  • Time complexity
  • Space complexity
• Conclusion
• References

A Binary Tree

A binary tree is a tree data structure in which each node has at most two children or child nodes, which are referred to as the left child and the right child. Another definition of a binary tree is that it is a tuple (L, S, R), where L and R are binary trees or the empty set and S is a singleton set containing the root.

The above binary tree is of size 7, with root node with value 1 and of height 3.

A symmetrical binary tree

In a binary tree data structure, each node has two subtrees, a left subtree and a right subtree which can be an empty subtree as well. A subtree can also be a single node or another binary tree. The whole binary tree is said to be symmetric if the root node's left subtree is an exact replicated reflection of the right subtree. For example, the below binary tree is a symmetric binary tree,

The binary tree below is not a symmetric binary tree as the left subtree of the root node is the exact copy (not the reflection) of the right subtree of the root node.

Recursive algorithm to check for symmetric binary tree

In this approach, we use a recursive function, is_mirror, to check whether two binary trees are exact mirror reflection of each other or not. The first thing, we do some checks to handle cases where at least one of the input binary trees is empty or not. Then, further, we apply the symmetricity rules on the two non-empty trees by recursively calling the is_mirror function. At the high level of recursion, we call the is_mirror function on our input binary tree's left subtree and the right subtree.

Steps of the algorithm

The algorithm first checks that the if the both the subtrees of the root node are empty, then they are mirror reflections. If not the algorithm moves to check whether the left subtrees and the right subtrees are empty or not, based on that it checks the mirror reflection of them. If both the subtrees are not none, it passes two recursive calls checking left subtree of first subtree and right subtree of the second subtree and then the other two for mirror reflections of each other. The algorithm recursively checks for each sub-binary tree to be the reflection of the other sub-binary tree, if not, returns the recursive call with boolean value false.

Implementation in Python

class Node:
	def __init__(self, key):
		self.key = key
		self.left = None
		self.right = None

# Returns True if trees with roots as root1 and root 2 are 
# mirror reflection of each other

def is_mirror(root1, root2):
	# If both trees are empty, then they are mirror 
    # reflections of each other, thus, the function should 
    # return True
	if root1 is None and root2 is None:
		return True

	# If the two trees are mirror reflections of each other   
    # then, their root node's key are same, left subtree of 
    # left tree and right subtree of the right tree are 
    # mirror reflections and right subtree of left tree and 
    # left subtree of right tree are mirror reflections of 
    # each other.
	if (root1 is not None and root2 is not None):
		if root1.key == root2.key:
			return (is_mirror(root1.left, root2.right) and is_mirror(root1.right, root2.left))

	# If none of the above conditions is true, then root1 and root2 are not mirror reflections
	return False

def is_symmetric(root):
    return is_mirror(root, root)

root = Node(1)
root.left = Node(2)
root.right = Node(2)
root.left.left = Node(3)
root.left.right = Node(4)
root.right.left = Node(4)
root.right.right = Node(3)
if is_mirror(root, root):
    print("The binary tree is symmetric.")
else:
    print("The binary tree is not symmetric.")

Time complexity for the recursive approach
The time complexity of the recursive algorithm for checking the binary tree to be symmetric is O(n), where n is the number of nodes in the tree as we traverse all the nodes of the tree.

Space complexity for the recursive approach
The space complexity of the recursive algorithm is O(h), where h refers to the height of the binary tree.

Iterative algorithm to check if a binary tree is symmetric

In this iterative approach, we construct a queue that contains the two child nodes of the root node. Then, in each iteration of the loop, we extract the two nodes in the front from the queue and compare their values. The right and left child nodes of the two nodes are inserted in the queue in the opposite order for future symmetric detections. We continue the process until all the tree nodes are traversed or unless we detect that the tree is not symmetric.

Steps of the algorithm

The algorithm first checks if the the root is none, if it is, then returns true as it is a symmetric binary tree. Then appends the left child value and right child value to the queue. Then runs a while loop until the queue is not empty repeats the above steps for check of the non-empty subtree and the adding the left child and right child of the nodes in the queue. When the nodes in the queue are all popped up, means the queue is empty, it indicates the tree is symmetric as at each iteration it checks for the reflection by checking the equality of the left child of one node and right child of the other. Otherwise, if the at an iteration, the values are not equal it returns the boolean value false.

Implementation in Python

class newNode:
	def __init__(self, key):
		self.key = key
		self.left = None
		self.right = None

def is_symmetric( root):
	if (root == None):
		return True
	
	if(not root.left and not root.right):
		return True
	
	q = []
	q.append(root)
	q.append(root)
	
	left_node = 0
	right_node = 0
	
	while(not len(q)):
		
		left_node = q[0]
		q.pop(0)
		
		right_node = q[0]
		q.pop(0)
		
		if(left_node.key != right_node.key):
			return False
		
		if(left_node.left and right_node.right) :
			q.append(left_node.left)
			q.append(right_node.right)
		
		elif (left_node.left or right_node.right) :
			return False
		
		if(left_node.right and right_node.left):
			q.append(left_node.right)
			q.append(right_node.left)
		
		elif (left_node.right or right_node.left):
			return False
	
	return True
	
root = newNode(1)
root.left = newNode(2)
root.right = newNode(2)
root.left.left = newNode(3)
root.left.right = newNode(4)
root.right.left = newNode(4)
root.right.right = newNode(3)

if (is_symmetric(root)) :
    print("The given tree is Symmetric")
else:
    print("The given tree is not Symmetric")

Time complexity for the iterative approach
Since, in the iterative approach also, we travese all the tree nodes. Thus, this approach too have the time complexity of O(n), where n is the total number of tree nodes.

Space complexity for the iterative approach
The space complexity of the iterative algorithm is O(h), where h refers to the height of the binary tree.

Conclusion

In this article at OpenGenus, we showed some algorithmic approaches to check if a binary tree is symmetric or not in a linear time with space complexity equal to the binary tree's height.