C# LeetCode 101: Symmetric Tree
Problem
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its centre).
Approach
To verify symmetry:
Left subtree of the root must be a mirror of the right subtree.
This means:
- Left child matches right child
- Left’s left matches right’s right
- Left’s right matches right’s left
We can simulate this comparison iteratively using two stacks instead of recursion.
1
/
2 2
/ /
3 4 4 3
Algorithm
Edge case: If the root is null → return true.
For the rest , we can:
Initialise two stacks to track nodes from the left and right subtrees.
Push root.left to the left stack and root.right to the right stack – this is our starting points.
Iterate while both stacks are not empty:
- Pop one node from each stack → compare them.
- If both are null, continue.
- If only one is null or values don’t match, return
false.
Push children in mirror order so the next pop compares mirrored nodes:
- Left stack:
leftNode.left,leftNode.right - Right stack:
rightNode.right,rightNode.left
If the loop ends without mismatches, the tree is symmetric.
Why This Works
By always pushing children in mirror order, the stacks pop() nodes that should mirror each other.
Any asymmetry (missing node or mismatched value) is caught immediately.
This approach avoids recursion, which can be beneficial for very deep trees.
Code
public bool IsSymmetric(TreeNode root)
{
if (root == null) return true;
var stackLeft = new Stack<TreeNode>();
var stackRight = new Stack<TreeNode>();
stackLeft.Push(root.left);
stackRight.Push(root.right);
while (stackLeft.Count > 0 && stackRight.Count > 0)
{
var leftNode = stackLeft.Pop();
var rightNode = stackRight.Pop();
if (leftNode == null && rightNode == null) continue;
if (leftNode == null || rightNode == null || leftNode.val != rightNode.val)
return false;
// Push children in mirror order
stackLeft.Push(leftNode.left);
stackLeft.Push(leftNode.right);
stackRight.Push(rightNode.right);
stackRight.Push(rightNode.left);
}
return stackLeft.Count == 0 && stackRight.Count == 0;
}
