LESSON 303 OF 347 · BINARY TREES

Symmetric Tree in C#: Mirror Check with Recursion

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

The number of nodes in the tree is in the range [1, 1000].
-100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?

STEP 1 OF 7

Guided

Ctrl + Enter to check

C# · BINARY TREES

Symmetric Tree in C#, explained

Problem overview

The method IsSymmetric receives the root of a binary tree and returns true when the tree is a mirror image of itself around its center. The values count, not just the shape.

The tree [1, 2, 2, 3, 4, 4, 3] is symmetric. The two children of the root both hold 2. The left 2 has children 3 and 4, and the right 2 has children 4 and 3, which is the same pair in the opposite order. The tree [1, 2, 2, null, 3, null, 3] is not: both 2s have a 3 on their right side only, and mirroring would require one of them to have its 3 on the left.

Approach: compare two subtrees that should mirror each other

Looking at one node is not enough, so the problem is turned into a question about two nodes: do these two subtrees mirror each other? Two subtrees a and b mirror each other when:

both are empty, or
both exist, hold the same value, the left child of a mirrors the right child of b, and the right child of a mirrors the left child of b.

Crossing the children is what makes it a mirror: the outer pair is compared together, and the inner pair is compared together. A whole tree is symmetric when its left half mirrors its right half. The lesson takes a shortcut: it asks whether the tree mirrors itself, by calling the helper with the root twice. The two arguments then start at the same node, and the helper walks down one copy going left while it walks down the other going right.

The follow up in the statement asks for an iterative version as well. That version uses a queue or stack of node pairs and checks the same conditions. This lesson shows the recursive version.

Step by step

Delegate in IsSymmetric. Return Dfs(root, root), which asks whether the tree mirrors itself.
Declare the helper above it: public bool Dfs(TreeNode root1, TreeNode root2). The two parameters are nodes that should mirror each other.
Both empty. If root1 == null && root2 == null, return true. Two empty subtrees always mirror each other, and this is the base case at the leaves.
Exactly one empty. If root1 == null || root2 == null, return false. Because the previous check handled the case of both being empty, at this point only one of them is, and that can't be symmetric.
Different values. If root1.val != root2.val, return false. Both nodes exist here, so reading their values is safe.
Outer pair. If Dfs(root1.left, root2.right) is false, return false right away. The inner pair needs no checking when the outer pair has failed.
Inner pair. Return Dfs(root1.right, root2.left). Its answer is the answer for the whole pair.

The solution in C#

class Solution {
    public bool Dfs(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null || root2 == null) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        if (!Dfs(root1.left, root2.right)) {
            return false;
        }
        return Dfs(root1.right, root2.left);
    }

    public bool IsSymmetric(TreeNode root) {
        return Dfs(root, root);
    }
}

C# details:

Order of the checks matters. The both-null check must come before the either-null check, and both must come before any .val access. Reading root1.val when root1 is null would throw a NullReferenceException.
Short-circuit operators. || and && stop evaluating as soon as the result is known. Here, that means the conditions are evaluated only on references that have already been compared.
Comparing with == on nodes. root1 == null checks the reference. The lesson's TreeNode is a class and doesn't overload ==, so this test is safe. Values are compared on the integer field val, which is what the mirror condition needs.
Returning a recursive call. The last line returns the result of Dfs directly instead of storing it in a variable and testing it.

Complexity

Time: O(n). Every node takes part in at most two pairs, once on each side of the mirror, and each pair costs constant work. The helper stops as soon as it finds a mismatch, so the worst case is a perfectly symmetric tree.

Space: O(h) for the recursion, where h is the height of the tree. For a balanced tree that is about log n, and for a chain it is n.

Edge cases and common mistakes

A single node. Dfs(root, root) sees equal values and then compares two null pairs, which return true. A one-node tree is symmetric.
Same shape, different values. [1, 2, 3] has a mirror shape but the children differ, so the value check returns false.
Same values, wrong shape. In [1, 2, 2, null, 3, null, 3] the values match pairwise but one side of a pair is empty and the other isn't, so the either-null check returns false.
Comparing left with left. Using Dfs(root1.left, root2.left) tests whether the two subtrees are identical, not mirrored. That would reject symmetric trees such as the first example.
Merging the two null checks. Writing only the either-null check returns false for two empty subtrees, so every leaf would fail.
Only checking values level by level. The mirror condition is about positions, not just which values appear on a level. [1, 2, 2, 3, null, 3, null], for example, has the right values on each level but is not symmetric.

Testing

[1, 2, 2, 3, 4, 4, 3] gives true.
[1, 2, 2, null, 3, null, 3] gives false.
[1] gives true.
[1, 2, 3] gives false.
[1, 2, 2] gives true.

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free