[Python] Simple BFS Iterative Approach with Explaination
Think in pairs would really help. \nTo check if a tree is symmetric, we need a BFS on 2 sides of symmetry: left and right. If left and right value match, we sho
Think in pairs would really help. \nTo check if a tree is symmetric, we need a BFS on 2 sides of symmetry: left and right. If left and right value match, we should proceed. \nThe key is to add the children of left and right in the proper order: outter match, then inner match. Because we are queuing in pairs, the children of inner pairs will match with the inner grandchildren, and so are the outter pairs. \n```\nclass Solution(object):\n    def isSymmetric(self, root):\n        """\n        :type root: TreeNode\n        :rtype: bool\n        """\n        \n        if not root:\n            return True\n        \n        queue = [root.left, root.right]\n        \n        while len(queue) > 0:\n            # pop 2 from queue\n            left = queue.pop(0)\n            right = queue.pop(0)\n            \n            # Evalate the pair\n            if not left and not right:\n                continue\n            elif left and right and left.val == right.val:\n                pass\n            else:\n                return False\n            \n            # Enqueue children\n            queue.append(left.left)\n            queue.append(right.right)\n            queue.append(left.right)\n            queue.append(right.left)\n        \n        return True\n```
['Breadth-First Search', 'Python']