LeetCode: Symmetric Tree C#

Question

https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/627

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

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

But the following [1,2,2,null,3,null,3] is not:

 1
 / \
 2 2
 \ \
 3 3

Note: Bonus points if you could solve it both recursively and iteratively.

using System.Collections.Generic;
using GraphsQuestions;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace TreeQuestions
{
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * public int val;
 * public TreeNode left;
 * public TreeNode right;
 * public TreeNode(int x) { val = x; }
 * }
 */
 /// <summary>
 /// https://leetcode.com/explore/interview/card/top-interview-questions-easy/94/trees/627
 /// </summary>
 [TestClass]
 public class SymmetricTreeTest
 {
 // 1
 // / \
 // 2 2
 // / \ / \
 // 3 4 4 3
 [TestMethod]
 public void ValidSymmetricTree()
 {
 TreeNode root = new TreeNode(1);
 root.left = new TreeNode(2);
 root.right = new TreeNode(2);
 root.left.left = new TreeNode(3);
 root.left.right = new TreeNode(4);
 root.right.left = new TreeNode(4);
 root.right.right = new TreeNode(3);
 Assert.IsTrue(SymmetricTree.IsSymmetric(root));
 }
 // 1
 // / \
 // 2 2
 // \ \
 // 3 3
 [TestMethod]
 public void NotValidSymmetricTree()
 {
 TreeNode root = new TreeNode(1);
 root.left = new TreeNode(2);
 root.right = new TreeNode(2);
 root.left.right = new TreeNode(3);
 root.right.right = new TreeNode(3);
 Assert.IsFalse(SymmetricTree.IsSymmetric(root));
 Assert.IsFalse(SymmetricTree.IsSymmetricIterative(root));
 }
 }
 public class SymmetricTree
 {
 public static bool IsSymmetric(TreeNode root)
 {
 if (root == null)
 {
 return true;
 }
 return Helper(root.left, root.right);
 }
 public static bool Helper(TreeNode t1, TreeNode t2)
 {
 if (t1 == null && t2 == null)
 {
 return true;
 }
 if (t1 == null || t2 == null)
 {
 return false;
 }
 if (t1.val != t2.val)
 {
 return false;
 }
 //make sure the MIRRORED SIDES are sent!
 return Helper(t1.left, t2.right) && Helper(t1.right, t2.left);
 }
 public static bool IsSymmetricIterative(TreeNode root)
 {
 if (root == null)
 {
 return true;
 }
 Queue<TreeNode> Q = new Queue<TreeNode>();
 Q.Enqueue(root);
 Q.Enqueue(root);
 while (Q.Count > 0)
 {
 TreeNode t1 = Q.Dequeue();
 TreeNode t2 = Q.Dequeue();
 if (t1 == null && t2 == null)
 {
 continue;
 }
 if (t1 == null || t2 == null)
 {
 return false;
 }
 if (t1.val != t2.val)
 {
 return false;
 }
 Q.Enqueue(t1.left);
 Q.Enqueue(t2.right);
 Q.Enqueue(t1.right);
 Q.Enqueue(t2.left);
 }
 return true;
 }
 }
}

Please review for performance

• David Fisher: This will be a top performer (it's correct). Good luck in the competition.
• Gilad: @DavidFisher which one?
• David Fisher: The iterator one is the great. However, humor me and just expand your tests down one additional branch. trying both: 1 2 3 4 4 3 2 1 and 1 2 2 1 3 4 4 3

Answer 1

Performance

• The recursive function is as fast as I can think of.
• The iterative function should enqueue root.left and root.right instead of root and root to gain a cycle (micro-optimisation).

Review

• I find it weird that the null node is considered symmetric IsSymmetric(null). I would throw an error for invalid input.
• Both algorithms are not able to deal with TreeNode instances that have a cycle (stack overflow exception vs infinite loop respectively). You will lose some performance if you guard against cycles.
• Helper is a public method. There is no reason for this. Make it private or local inside the public method, and perhaps rename it to IsSymmetric, which will not be in conflict with the public method because of different signature.
• Parameter names t1 and t2 are best avoided. Use full and more clear names like node1 and node2.
• Queue<TreeNode> Q = new Queue<TreeNode>(); should be written more concisely and clearly as var queue = new Queue<TreeNode>();.