This code is a C# implementation of a solution to the problem of checking if a binary tree is symmetric or not. A binary tree is symmetric if it is a mirror image of itself along the center. For example, this tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
The code has two methods: 'IsSymmetricIterative' and 'IsSymmetricRecursion', which use different approaches to solve the problem.
The 'IsSymmetricIterative' method uses a queue data structure to store the nodes of the tree in pairs, such that each pair consists of two nodes that should be mirror images of each other. For example, the first pair is the left and right children of the root, the second pair is the left child of the left child and the right child of the right child, and so on. The method then dequeues each pair and checks if they are both null, which means they are symmetric, or if they have the same value, which means they are also symmetric. If either of them is null or they have different values, then the method returns false, as the tree is not symmetric. The method repeats this process until the queue is empty or it finds a pair that is not symmetric.
The 'IsSymmetricRecursion' method uses a helper method called 'SymmetricHelper', which takes two nodes as parameters and returns true if they are symmetric, or false otherwise. The method first checks if the root is null, in which case it returns true, as an empty tree is symmetric. Then it calls the helper method with the right and left children of the root. The helper method recursively checks if the two nodes are both null, which means they are symmetric, or if they have the same value and their subtrees are also symmetric. It does this by calling itself with the left child of the left node and the right child of the right node, and with the right child of the left node and the left child of the right node. If any of these conditions are not met, then the helper method returns false, as the nodes are not symmetric.
#region iterative
public bool IsSymmetricIterative(TreeNode root)
{
// iterative solution
// just basic level traversal is used only little variation is while adding elements to the queue take care.
Queue<TreeNode> treeNodes = new Queue<TreeNode>();
treeNodes.Enqueue(root.left);
treeNodes.Enqueue(root.right);
while(treeNodes.Count > 0)
{
TreeNode left = treeNodes.Dequeue(),right = treeNodes.Dequeue();
if (left == null && right == null)
continue;
if(left == null || right == null)
return false;
if(left.val != right.val)
return false;
// enqueue the element in a way such that they are mirror elements
treeNodes.Enqueue(left.left);
treeNodes.Enqueue(right.right);
treeNodes.Enqueue(left.right);
treeNodes.Enqueue(right.left);
}
return true;
}
#endregion
#region recursion
public bool IsSymmetricRecursion(TreeNode root)
{
return root == null || SymmetricHelper(root.right,root.left);
}
private bool SymmetricHelper(TreeNode right, TreeNode left)
{
if(right == null && left == null )
return true;
if(right == left || left == null) return false;
return (right.val == left.val) && SymmetricHelper(left.left,right.right) && SymmetricHelper(left.right,right.left);
}
Both methods have a time complexity of O(n), where n is the number of nodes in the tree, as they visit each node once. They also have a space complexity of O(n), as they use extra space to store the nodes in a queue or in a call stack.