A binary tree is called symmetric if it is a mirror of itself. In other words, a tree is symmetric if its left and right subtrees are mirrors of each other. This symmetry needs to be recursively true for all nodes in the tree.

For this to be clearer, consider the following tree:

    1
   / \
  2   2
 / \ / \
3  4 4  3

This tree is symmetric. Now, if we changed the last 3 to another number, it wouldn’t be symmetric anymore.

Checking Symmetry in C#

How can we check if a binary tree is symmetric in C#?

Let’s first define our basic tree structure:

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

To check if the tree is symmetric, we need to compare the left and right subtrees for equality. But the comparison isn’t straightforward. For two subtrees to be symmetric, the following conditions must be true:

1. Their root values should be equal.
2. The left subtree of the left tree should be symmetric to the right subtree of the right tree.
3. The right subtree of the left tree should be symmetric to the left subtree of the right tree.

Here’s a C# function that checks for symmetry:

public bool IsSymmetric(TreeNode root) {
    return root == null || CheckSymmetry(root.left, root.right);
}

private bool CheckSymmetry(TreeNode left, TreeNode right) {
    if (left == null && right == null) return true;
    if (left == null || right == null) return false;

    return (left.val == right.val) 
        && CheckSymmetry(left.left, right.right) 
        && CheckSymmetry(left.right, right.left);
}

Understanding the Code

The main IsSymmetric function is straightforward. If the tree has no nodes, it’s symmetric. Otherwise, it delegates the check to the CheckSymmetry function, which compares the left and right subtrees.

CheckSymmetry checks recursively:

1. If both nodes are null, they’re symmetric (base case).
2. If one node is null and the other isn’t, they’re not symmetric.
3. If the values are different, they’re not symmetric.
4. Recursively check the subtrees, as per the conditions outlined above.

Symmetric trees present an interesting property of binary trees where the tree remains invariant when reflected. Understanding such properties and classifications is essential as they often form the basis for many algorithms and problem-solving approaches in computer science. By understanding the basics and practicing with examples like the C# code above, you’ll be better equipped to tackle problems related to tree structures in your future coding endeavors.