Author: admin

Find if two strings are anagrams

admin / / Data Structures, Strings

© Parineeth M R

Question 23. Find if two string words are anagrams of each other

Two strings are anagrams of each other if re-arrangement of characters in one string results in the other string. This implies that two string words are anagrams if for each character, the number of times the character occurs in the first string is equal to the number of times it occurs in the second string. The code for finding if two words are anagrams is given below

C/C++


/*str1, str2: the two non-NULL strings which we want to compare
Return value: 1 if the two strings are anagrams, 0 otherwise
*/
int are_strings_anagrams( char *str1, char *str2)
{
	int count1[NUM_CHARACTERS], count2[NUM_CHARACTERS];
	int is_anagram, i;

	/*Initilize the counts to zero */
	memset(count1, 0, sizeof(int) * NUM_CHARACTERS);
	memset(count2, 0, sizeof(int) * NUM_CHARACTERS);
	
	/*Compute the character counts for str1 and str2*/
	while (*str1) {
		count1[(int)*str1]++;
		str1++;
	}
	
	while (*str2) {
		count2[(int)*str2]++;
		str2++;
	}
	
	/*Compare the counts*/
	is_anagram = 1;
	for (i = 0; i < NUM_CHARACTERS; ++i) {
		if (count1[i] != count2[i]) {
			is_anagram = 0;
			break;
		}
	}
	return is_anagram;
}

Java


/*
str1, str2: the two strings which we want to compare
Return value: true if the two strings are anagrams, false otherwise
*/
public static boolean areAnagrams( char[] str1, char[] str2) 	{
	/*Initilize the counts to zero */
	int[] count1 = new int[NUM_CHARACTERS]; //NUM_CHARACTERS is 256
	int[] count2 = new int[NUM_CHARACTERS];

	/*Compute the character counts for str1 and str2*/
	for (char c: str1) 
		count1++;

	for (char c : str2) 
		count2++;

	/*Compare the counts*/
	boolean isAnagram = true;
	for (int i = 0; i < NUM_CHARACTERS; ++i) {
		if (count1[i] != count2[i]) {
			isAnagram = false;
			break;
		}
	}

	return isAnagram;
}

Python


#str1, str2: the two strings which we want to compare
#Return value: True if the two strings are anagrams, False otherwise
def are_anagrams(str1, str2) :	
	count1 = [0] * NUM_CHARACTERS #NUM_CHARACTERS is 256
	count2 = [0] * NUM_CHARACTERS

	#Compute the character counts for str1 and str2
	for  c in str1:
		count1[ord(c)] += 1
	

	for  c in str2:
		count2[ord(c)] += 1
	
	#Compare the counts
	is_anagram = True
	if (count1 != count2):
		is_anagram = False
		
	return is_anagram

Rotate an array

admin / / Arrays, Data Structures

© Parineeth M R

Question 22. Rotate an array by k times

Consider the array {10, 20, 30, 40, 50}. Suppose we rotate the array once, we have to move the elements 10, 20, 30, 40 right by 1 position and move the last element 50 to the beginning to get {50, 10, 20, 30, 40}. So if we have an array of size n, then for 1 rotate operation we will need n moves. If we rotate the array k times then there will be k*n moves. There is a faster method for rotating an array. Let the array be A = {10, 20, 30, 40, 50} and the number of rotations k = 2. The procedure is:

1. Reverse the entire array. So we get {50, 40, 30, 20, 10}

2. Reverse the array in the region 0 to k -1. If k = 2, we reverse the region A[0] to A[1]. So we get the array {40, 50, 30, 20, 10}

3. Finally reverse the array in the region k to n-1 where n is the length of the array. If k=2, we reverse the region A[2] to A[4]. So we get the required result {40, 50, 10, 20, 30}.

With this technique, we always need 2*n moves irrespective of the value of k.

C/C++


/*Main function to rotate a 1 dimensional array
a: array which should be rotated. 
length: number of elements in the array. Should be > 0
num_rotations: how many times to rotate the array. Should be >= 0
*/
void rotate_array(int a[], int length, int num_rotations)
{
	/*Suppose an array has a length of 5, every time we rotate by 5 
	locations, we end up with the same array. So obtain num_rotations 
	value from 0 to length - 1*/
	num_rotations = num_rotations % length;

	if (num_rotations == 0)
		return;

	reverse_array(a, 0, length - 1);

	reverse_array(a, 0, num_rotations - 1);

	reverse_array(a, num_rotations, length - 1);
}

Java


/*Main function to rotate a 1 dimensional array
a: array which should be rotated. 
numRotations: how many times to rotate the array. Should be >= 0
*/
public static void rotateArray(int[] a, int numRotations) {
	int length = a.length;
	if (length == 0)
		return;

	/*Suppose an array has a length of 5, every time we rotate by 
	5 locations, we end up with the same array. So obtain numRotations 
	value from 0 to length - 1*/
	numRotations = numRotations % length;

	if (numRotations == 0)
		return;

	reverseArray(a, 0, length - 1);

	reverseArray(a, 0, numRotations - 1);

	reverseArray(a, numRotations, length - 1);
}

Python


#Main function to rotate a 1 dimensional list
#a: list which should be rotated. 
#num_rotations: how many times to rotate the list. Should be >= 0
def rotate_list(a, num_rotations) :
	length = len(a)
	if (length == 0):
		return

	#Suppose a list has a length of 5, every time we rotate by 
	#5 locations, we end up with the same list. So obtain num_rotations 
	#value from 0 to length - 1
	num_rotations = num_rotations % length

	if (num_rotations == 0):
		return

	reverse_list(a, 0, length - 1)

	reverse_list(a, 0, num_rotations - 1)

	reverse_list(a, num_rotations, length - 1)


#Helper function which reverses a list in region (low, high)
#a: list which needs to be reversed
#low: lower index of region to be reversed
#high: higher index of region to be reversed
def reverse_list(a, low, high) :
	while (low < high) :
		a[low], a[high] = a[high], a[low]
		low += 1
		high = high - 1

Move all zeroes to one end

admin / / Arrays, Data Structures

© Parineeth M R

Question 21. Move all the zeroes in an array to the right end of the array

We can move all the zeroes to one end of the array (in this case, the right end) in O(n) using the following technique:

1. Scan for the first zero from the left side of the array.

2. Scan for the first non-zero from the right side of the array.

3. Swap the zero and non-zero provided that the zero appears to the left of the non-zero

C/C++


/*
a: input array in which the zeroes should be moved to one end
length: number of elements in array a 
*/
void move_zeroes(int a[], int length)
{
	int left, right;

	left = 0;
	right = length - 1;

	while (left < right) {
		/*Locate the first zero from the left*/
		while (left < length && a[left] != 0)
			left++;

		/*Locate first non-zero from the right*/
		while (right >= 0 && a[right] == 0)
			right--;

		if (left < right) {
			/*Swap a[left] and a[right]*/
			int temp = a[left];
			a[left] = a[right];
			a[right] = temp;
		}
	}
}

Java


/*
a: input array in which the zeroes should be moved to one end
*/
public static void moveZeroes(int[] a) {
	int length = a.length;

	int left = 0;
	int right = length - 1;

	while (left < right) {
		/*Locate the first zero from the left*/
		while (left < length && a[left] != 0)
			left++;

		/*Locate first non-zero from the right*/
		while (right >= 0 && a[right] == 0)
			right--;

		if (left < right) {
			/*Swap a[left] and a[right]*/
			int temp = a[left];
			a[left] = a[right];
			a[right] = temp;
		}
	}
}

Python


#a: input list in which the zeroes should be moved to one end
def move_zeroes(a) :
	length = len(a)

	left = 0
	right = length - 1

	while (left < right) :
		#Locate the first zero from the left
		while (left < length and a[left] != 0):
			left += 1

		#Locate first non-zero from the right
		while (right >= 0 and a[right] == 0):
			right = right - 1

		if (left < right) :
			#Swap a[left] and a[right]
			a[left], a[right] = a[right], a[left]

Remove all duplicates from an array

admin / / Arrays, Data Structures

© Parineeth M R

Question 20. Given an array, remove all the duplicates from the array

Suppose the given array is A = {1, 4, 2, 1, 5, 2} and we have to remove all duplicates from it, then the result array is {1, 4, 2, 5}. All duplicates in an array A can be removed using the following approaches

1. Brute force approach. Pick every element in A and remove all the duplicates of that element. Removing all duplicates of one element can be done in O(n). Since we have to do this for n elements, the time complexity will be O(n2) and no extra space is needed

2. Hash table approach. Traverse the elements in A and add the elements to a hash table. If we encounter an element which is already in the hash table, then we exclude it from the result. The time complexity is O(n) but we will need extra space for the hash table.

3. Sorting. Sort the array A. After sorting, the duplicates will be arranged next to each other. Then iterate through the sorted array and retain an element in A only if it is different from the previous element. We will be using this approach in the code below. The time complexity is O(nlog(n)) and we don’t need additional space.

C/C++


/*
a: non-empty array from which duplicates should be removed. 
	this array will be modified in-place
length: number of elements in array a 
Returns: number of elements in array a after removing duplicates 
*/
int remove_duplicates(int a[], int length)
{
	int i, fill_pos;

	/*Sort the array*/
	sort(a, length);

	fill_pos = 1;
	for (i = 1; i < length; ++i) {
		if (a[i] != a[i - 1]) {
			a[fill_pos] = a[i];
			fill_pos++;
		}
	}

	return fill_pos;
}

Java


/*
a: non-empty input array from which duplicates should be removed. 
	this array will be modified
Returns: new output array which doesn't have duplicates 
*/
public static int[] removeDuplicates(int[] a) {
	int length = a.length;

	/*Sort the array*/
	Arrays.sort(a);

	int fillPos = 1;
	for (int i = 1; i < length; ++i) {
		if (a[i] != a[i - 1]) {
			a[fillPos] = a[i];
			fillPos++;
		}
	}

	int[] result = Arrays.copyOf(a, fillPos);
	return result;
}

Python


#a: non-empty input list from which duplicates should be removed. 
#	this list will be modified in-place
def remove_duplicates(a) :
	length = len(a)

	#Sort the list
	a.sort()

	fill_pos = 1
	for  i in range(1, length):
		if (a[i] != a[i - 1]) :
			a[fill_pos] = a[i]
			fill_pos += 1

	#remove the remaining items in the list from fill_pos onwards
	if (fill_pos < length):		
		del a[fill_pos:]

Remove all occurrences of an element from an array

admin / / Arrays, Data Structures

© Parineeth M R

Question 19. Given an array, remove all occurrences of an element from the array

Suppose the given array is A = {1, 4, 2, 1, 5, 2} and we have to remove all occurences of 1 from it, then the result array is {4, 2, 5, 2}. The element to be removed from the array can be present in multiple locations. We can efficiently remove all occurrences of the element in O(1) space and O(n) time in a single pass through the array by doing the following:

1. Maintain a variable called fill_pos to keep track of where we should store the next element of the array that should not be deleted. Initialize fill_pos to 0.

2. Traverse through the array. If the current element in the array should be deleted then skip it. If current element in the array should not be deleted, then store the current element at fill_pos in the array and increment fill_pos

C/C++


/*
a: input array from which all occurrences of an element should be removed
length: number of elements in array a 
x: element to be removed
Return value: number of elements in a after removing x 
*/
int remove_element(int a[], int length, int x)
{
	int i, fill_pos;

	fill_pos = 0;
	for (i = 0; i < length; ++i) {
		if (a[i] != x) {
			a[fill_pos] = a[i];
			fill_pos++;
		}
	}

	return fill_pos;
}

Java


/*
a: input array from which all occurrences of an element should be removed
x: element to be removed
Return value: output array after removing x 
*/
public static int[] removeElement(int[] a, int x) {
	int fillPos = 0;
	for (int i = 0; i < a.length; ++i) {
		if (a[i] != x) {
			a[fillPos] = a[i];
			fillPos++;
		}
	}

	int[] result = Arrays.copyOf(a, fillPos);
	return result;
}

Python


#a: input list from which all occurrences of an element should be removed
#x: element to be removed
def remove_element(a, x) :
	length = len(a)
	fill_pos = 0
	for  i in range(0, length):
		if (a[i] != x) :
			a[fill_pos] = a[i]
			fill_pos += 1
	
	#delete all the elements from fill_pos onwards	
	if (fill_pos < length) :
		del a[fill_pos:]

Replace each element with next greatest

admin / / Arrays, Data Structures

© Parineeth M R

Question 18. Replace each element in an array with the next greatest

Consider the array A = {0, 2, 8, 1, 3, 5, 4}.

The greatest number after 0 in A is maximum of {2, 8, 1, 3, 5, 4} = 8. So 0 is replaced by 8.

The greatest number after 8 in A is maximum of {1, 3, 5, 4} = 5. So 8 is replaced with 5.

4 is the last number in A. There are no more elements to its right. So 4 is replaced by an invalid number or the smallest possible number.

So the resulting array is = {8, 8, 5, 5, 5, 4, INVALID_NUMBER}.

The brute force approach will try to compute the next greatest of an element by scanning all the elements to its right. This will have a time complexity of O(n2).

However we can achieve the same in O(n) by traversing from the end of the array to the beginning and maintaining the maximum element seen so far. The code is given below

C/C++


/*
a: array in which each element should be replaced with next greatest
n: number of elements in the array. n >= 1
*/
void replace_with_next_greatest(int a[], int n) {
	int i, next_greatest, temp;

	next_greatest = a[n-1];
	a[n-1] = INVALID_NUMBER;  

	/*Process the array from backwards*/
	for (i = n-2; i >= 0; --i) {
		temp = a[i];

		a[i] = next_greatest;

		if (temp > next_greatest)
			next_greatest = temp;
	}
}

Java


/*
a: non-empty array in which each element should be replaced with next greatest
*/
public static void replaceWithNextGreatest(int[] a) {
	int n = a.length;
	int nextGreatest = a[n-1];
	a[n-1] = INVALID_NUMBER;  

	/*Process the array backwards*/
	for (int i = n-2; i >= 0; --i) {
		int temp = a[i];

		a[i] = nextGreatest;

		if (temp > nextGreatest)
			nextGreatest = temp;
	}
}

Python


#a: non-empty list in which each element should be replaced with next greatest
def replace_with_next_greatest(a) :
	n = len(a)

	next_greatest = a[n-1]
	a[n-1] = INVALID_NUMBER  

	#Process the list from the back
	for i in range(n-2, -1, -1) :
		temp = a[i]

		a[i] = next_greatest

		if (temp > next_greatest):
			next_greatest = temp

Print binary tree in level order

admin / / Data Structures, Trees

© Parineeth M R

Question 17. Print the nodes of a binary tree in level order

To print the nodes of the binary tree in level order, we start with the root node and then print the child nodes in each level from left to right. Consider the binary tree below

The level order printing will result in the following output: ABCDEFG. To achieve this we make use of a queue and use the following strategy:

1. Add the root node to the queue

2. Remove the head element of the queue and print it. Then add the children of the removed element back to the queue. Repeat step-2 till the queue becomes empty.

C/C++


/*
root: root node of the tree 
q: queue that helps in printing in level order
*/
void print_level_order(struct node *root, queue<struct node*>& q)
{
	struct node *n;
	int num_nodes_in_cur_level, num_nodes_in_next_level;

	if (!root)
		return;

	/*Add the root node to the empty queue*/
	q.push(root);
	num_nodes_in_cur_level = 1;
	num_nodes_in_next_level = 0;

	/*Process the nodes in the queue in Breadth First manner*/
	while (!q.empty()) {

		/*Remove the node at the head of the queue*/
		n = q.front();
		q.pop();

		print_data(n->data); /*print the data in the node*/

		/*Add the left child to the end of the queue*/
		if (n->left) {
			q.push(n->left);
			num_nodes_in_next_level++;
		}

		/*Add the right child to the end of the queue*/
		if (n->right) {
			q.push(n->right);
			num_nodes_in_next_level++;
		}

		num_nodes_in_cur_level--;

		/*go to next line, if all nodes in current level are processed*/
		if (num_nodes_in_cur_level == 0) {
			cout << endl;
			num_nodes_in_cur_level = num_nodes_in_next_level;
			num_nodes_in_next_level = 0;
		}
	}
}

Java


/*
root: root node of the tree 
q: queue used for printing the tree 
*/
public static void printLevelOrder(TreeNode root, Queue<TreeNode> q) {
	if (root == null)
		return;

	/*Add the root node to the empty queue*/
	q.add(root);
	int numNodesInCurLevel = 1;
	int numNodesInNextLevel = 0;

	/*Process the nodes in the queue in Breadth First manner*/
	while (!q.isEmpty()) {

		/*Remove the node at the head of the queue*/
		TreeNode n = q.remove();

		printData(n.data); /*print the data in the node*/

		/*Add the left child to the queue*/
		if (n.left != null) {
			q.add(n.left);
			numNodesInNextLevel++;
		}

		/*Add the right child to the queue*/
		if (n.right != null) {
			q.add(n.right);
			numNodesInNextLevel++;
		}

		numNodesInCurLevel--;

		/*go to next line, if all nodes in current level are processed*/
		if (numNodesInCurLevel == 0) {
			System.out.println();
			numNodesInCurLevel = numNodesInNextLevel;
			numNodesInNextLevel = 0;
		}
	}
}

Python


#root: root node of the tree 
#q: Python Queue object used for printing the tree
@staticmethod
def print_level_order(root, q):
	if (not root):
		return

	#Add the root node to the empty queue
	q.put(root)
	num_nodes_in_cur_level = 1
	num_nodes_in_next_level = 0

	#Process the nodes in the queue in Breadth First manner
	while (not q.empty()) :
		#Remove the node at the head of the queue
		n = q.get()

		TreeNode.print_data(n.data) #print the data in the node

		#Add the left child to the queue
		if (n.left) :
			q.put(n.left)
			num_nodes_in_next_level += 1
		
		#Add the right child to the queue
		if (n.right) :
			q.put(n.right)
			num_nodes_in_next_level += 1
		
		num_nodes_in_cur_level = num_nodes_in_cur_level - 1

		#go to next line, if all nodes in current level are processed
		if (num_nodes_in_cur_level == 0) :
			print('')
			num_nodes_in_cur_level = num_nodes_in_next_level
			num_nodes_in_next_level = 0

Find if a binary tree is a binary search tree

admin / / Data Structures, Trees

© Parineeth M R

Question 16. Find if a binary tree is a binary search tree

The initial approach that comes to mind is to check if the left child node is smaller than the parent node and the right child node is greater than the parent node for all the nodes in the tree. However this solution will not work as shown in the binary tree above. Every node satisfies the condition that the left child is smaller than the parent and the right child is greater than the parent. But the tree is still not a binary search tree since node 9 is incorrect. To correctly find out if a tree is a binary search tree, we should traverse the tree in-order and check if the nodes are present in ascending order

C/C++


/*cur_node: current node whose left and right sub-trees need to be checked
prev_node_pp: the in-order predecessor of cur_node
Return value: 1 if the tree is a binary search tree, 0 otherwise
*/
int is_bst(struct node *cur_node, struct node ** prev_node_pp)
{
	if (!cur_node)
		return 1;

	/*Check if the left sub-tree is a BST*/
	if (!is_bst(cur_node->left, prev_node_pp)) 
		return 0;

	/*If data in cur_node is <= to previous node then it is not a BST*/
	if (*prev_node_pp && cur_node->data <= (*prev_node_pp)->data)
		return 0;

	/*Update previous node to current node*/
	*prev_node_pp = cur_node;

	/*Check if the right sub-tree is a BST*/
	return is_bst(cur_node->right, prev_node_pp); 
}

Java


/*curNode: current node 
prevNodeArray: in-order predecessor of curNode is present in prevNodeArray[0]
Return value: true if the tree is a binary search tree, false otherwise
*/
public static boolean isBst(TreeNode curNode, TreeNode[] prevNodeArray)  {
	if (curNode == null)
		return true;

	/*Check if the left sub-tree is a BST*/
	if (!isBst(curNode.left, prevNodeArray)) 
		return false;

	/*If data in curNode is <= previous node then it is not a BST*/
	TreeNode prevNode = prevNodeArray[0];
	if (prevNode != null && curNode.data <= prevNode.data)
		return false;

	/*Update previous node to current node*/
	prevNodeArray[0] = curNode;

	/*Check if the right sub-tree is a BST*/
	return isBst(curNode.right, prevNodeArray); 
}

Python


#cur_node: current node 
#prev_node_list: prev_node_list[0] has in-order predecessor of cur_node 
#Return values: True if the tree is a binary search tree, False otherwise
@staticmethod
def is_bst(cur_node, prev_node_list):
	if (not cur_node):
		return True

	#Check if the left sub-tree is a BST
	if (not TreeNode.is_bst(cur_node.left, prev_node_list)): 
		return False

	#If data in cur_node is <= previous node then it is not a BST
	prev_node = prev_node_list[0]
	if (prev_node and cur_node.data <= prev_node.data):
		return False

	#Update previous node to current node
	prev_node_list[0] = cur_node

	#Check if the right sub-tree is a BST
	return TreeNode.is_bst(cur_node.right, prev_node_list)

Is binary tree balanced

admin / / Data Structures, Trees

© Parineeth M R

Question 15. Find if a binary tree is balanced

A binary tree is balanced if at every node in the tree, the absolute difference between the height of the left-subtree and the height of the right sub-tree doesn’t exceed 1. To solve the problem we recursively traverse the tree and calculate the height of the nodes in a bottom up manner. If at any node, the difference between the height of the left and right sub-trees exceeds 1, we report that the tree is unbalanced.

C/C++


/*cur_node: node of the binary tree being checked
height: height of the current node is returned here
Return value: 1 if the tree is balanced, 0 otherwise
*/
int is_balanced(struct node *cur_node, int *height)
{
	int is_left_balanced, is_right_balanced;
	int left_height, right_height;

	if (!cur_node) {
		*height = 0;
		return 1;
	}

	is_left_balanced = is_balanced(cur_node->left, &left_height);
	is_right_balanced = is_balanced(cur_node->right, &right_height);

	if (!is_left_balanced || !is_right_balanced)
		return 0;

	/*If the difference between height of left subtree and height of
	right subtree is more than 1, then the tree is unbalanced*/
	if (abs(left_height - right_height) > 1)
		return 0;

	/*To get the height of the current node, we find the maximum of the  
	left subtree height and the right subtree height and add 1 to it*/
	*height = max(left_height, right_height) + 1;

	return 1;	
}

Java


/*curNode: node of the binary tree being checked
height: height of the curNode is returned here
Return value: true if the tree is balanced, false otherwise
*/
public static boolean isBalanced(TreeNode curNode, Int height) {
	Int leftHeight = new Int();
	Int rightHeight = new Int();

	if (curNode == null) {
		height.value = 0;
		return true;
	}


	boolean isLeftBalanced = isBalanced(curNode.left, leftHeight);
	boolean isRightBalanced = isBalanced(curNode.right, rightHeight);

	if (!isLeftBalanced || !isRightBalanced)
		return false;

	/*If the difference between height of left subtree and height of
	right subtree is more than 1, then the tree is unbalanced*/
	if (Math.abs(leftHeight.value - rightHeight.value) > 1)
		return false;

	/*To get the height of the current node, we find the maximum of the  
	left subtree height and the right subtree height and add 1 to it*/
	height.value = Math.max(leftHeight.value, rightHeight.value) + 1;

	return true;	
}

Python


#cur_node: node of the binary tree being checked
#Return values: 1. True if the tree is balanced, False otherwise
#		2. height of the cur_node is also returned
@staticmethod
def is_balanced(cur_node) :
	if (not cur_node) :
		height = 0
		return True, height
	
	is_left_balanced, left_height = TreeNode.is_balanced(cur_node.left)
	is_right_balanced, right_height = TreeNode.is_balanced(cur_node.right)

	#To get the height of the current node, we find the maximum of the  
	#left subtree height and the right subtree height and add 1 to it
	height = max(left_height, right_height) + 1

	if (not is_left_balanced or not is_right_balanced):
		return False, height

	#If the difference between height of left subtree and height of
	#right subtree is more than 1, then the tree is unbalanced
	if (abs(left_height - right_height) > 1):
		return False, height
	
	return True, height

Is binary tree symmetric

admin / / Data Structures, Trees

© Parineeth M R

Question 14. Find if a binary tree is symmetric

A binary tree is symmetric, if the left sub-tree of each node is a mirror image of the right sub-tree. An example of a symmetric binary tree is given below

C/C++


int compare_nodes ( struct node *n1, struct node *n2) {
	if (!n1 && !n2)  /*If both the nodes are NULL */
		return 1;  /* return symmetric*/
	
	if ( (n1 && !n2) || (!n1 && n2)) /*If one node is NULL and other is not*/
		return 0; /*return not symmetric*/
	
	if (n1->data != n2->data) /*If data of two nodes don't match */
		return 0; /* return not symmetric */
		
	if (!compare_nodes (n1->left, n2->right)) 
		return 0;
	
	if (!compare_nodes (n1->right, n2->left)) 
		return 0;
	
	return 1; /*Return symmetric*/
}

/*Returns 1 if the tree is symmetric, 0 otherwise*/
int is_symmetric(struct node * root) {
	if (!root)
		return 1;
	
	return compare_nodes(root->left, root->right);
}

Java


public static boolean compareNodes ( TreeNode n1, TreeNode n2) {
	if (n1 == null && n2 == null)  /*If both the nodes are null */
		return true;  /* return symmetric*/

	/*If one node is null and the other is not null*/
	if ( (n1 != null && n2 == null) || (n1 == null && n2 != null))  
		return false; /*return not symmetric*/

	if (n1.data != n2.data) /*If data of two nodes don't match */
		return false; /* return not symmetric */
	
	if (!compareNodes (n1.left, n2.right)) 
		return false;

	if (!compareNodes (n1.right, n2.left))
		return false;

	return true; /*Return symmetric*/
}

/*Returns true if the tree is symmetric, false otherwise*/
public static boolean isSymmetric(TreeNode root) {
	if (root == null)
		return true;

	return compareNodes(root.left, root.right);
}

Python


@staticmethod
def compare_nodes(n1, n2): 
	if (not n1 and not n2):  #If both the nodes are None
		return True  # return symmetric

	#If one node is None and the other is not None
	if ( (n1 and not n2) or (not n1 and n2)):  
		return False #return not symmetric

	if (n1.data != n2.data): #If data of two nodes don't match
		return False # return not symmetric 
	
	if (not TreeNode.compare_nodes(n1.left, n2.right)): 
		return False

	if (not TreeNode.compare_nodes(n1.right, n2.left)): 
		return False

	return True #Return symmetric


@staticmethod
#Returns True if the tree is symmetric, False otherwise
def is_symmetric(root): 
	if (not root):
		return True

	return TreeNode.compare_nodes(root.left, root.right)