4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ This will be a top performer (it's correct). Good luck in the competition. \$\endgroup\$ – David Fisher Sep 19 '19 at 19:23
  • \$\begingroup\$ @DavidFisher which one? \$\endgroup\$ – Gilad Sep 19 '19 at 21:00
  • \$\begingroup\$ 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 \$\endgroup\$ – David Fisher Sep 21 '19 at 1:18
6
\$\begingroup\$

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>();.
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.