Symmetric Tree

Data Structures and Algorithms

Statement

Given the root of a binary tree, find whether it’s symmetric. A symmetric tree is a mirror of itself around the root.

Constraints

• 1 ≤ number of nodes ≤ 500
• -10³ ≤ node.data ≤ 10³

Solution

"""
production algorithm
"""

from data_structures.queue.queue import Queue


class Solution:
    def is_symmetric(self, root):
        """
        time complexity O(n)
        space complexity O(n)
        """
        queue = Queue()
        queue.push(root.left)
        queue.push(root.right)
        while not queue.empty():
            left, right = queue.pop(), queue.pop()
            if left and not right or\
                    not left and right or\
                    left and right and not left.data == right.data:
                return False
            if left and right:
                queue.push(left.left)
                queue.push(right.right)
                queue.push(left.right)
                queue.push(right.left)
        return True

"""
unit tests
"""

from unittest import TestCase
from algorithms.bfs.symmetric_tree.solution import Solution
from data_structures.binary_tree.binary_tree import BinaryTreeNode


class SolutionTestCase(TestCase):
    def test_left_skewed_tree(self):
        # Given
        root = BinaryTreeNode(1)
        root.left = BinaryTreeNode(3)
        root.right = BinaryTreeNode(3)
        root.left.left = BinaryTreeNode(5)
        root.left.right = BinaryTreeNode(5)
        root.right.left = BinaryTreeNode(5)
        root.right.right = BinaryTreeNode(5)
        root.left.left.left = BinaryTreeNode(7)
        root.left.left.right = BinaryTreeNode(7)
        root.left.right.left = BinaryTreeNode(7)
        root.left.right.right = BinaryTreeNode(7)
        solution = Solution()

        # When
        actual = solution.is_symmetric(root)

        # Then
        expected = False
        self.assertEqual(actual, expected)

    def test_data_mismatch(self):
        # Given
        root = BinaryTreeNode(1)
        root.left = BinaryTreeNode(3)
        root.right = BinaryTreeNode(3)
        root.left.left = BinaryTreeNode(5)
        root.left.right = BinaryTreeNode(5)
        root.right.left = BinaryTreeNode(7)
        root.right.right = BinaryTreeNode(7)
        solution = Solution()

        # When
        actual = solution.is_symmetric(root)

        # Then
        expected = False
        self.assertEqual(actual, expected)

    def test_binary_tree_succeeds(self):
        # Given
        root = BinaryTreeNode(1)
        root.left = BinaryTreeNode(3)
        root.right = BinaryTreeNode(3)
        root.left.left = BinaryTreeNode(5)
        root.right.right = BinaryTreeNode(5)
        root.left.left.left = BinaryTreeNode(7)
        root.right.right.right = BinaryTreeNode(7)
        solution = Solution()

        # When
        actual = solution.is_symmetric(root)

        # Then
        expected = True
        self.assertEqual(actual, expected)

    def test_perfect_binary_tree_succeeds(self):
        # Given
        root = BinaryTreeNode(1)
        root.left = BinaryTreeNode(3)
        root.right = BinaryTreeNode(3)
        root.left.left = BinaryTreeNode(5)
        root.left.right = BinaryTreeNode(7)
        root.right.left = BinaryTreeNode(7)
        root.right.right = BinaryTreeNode(5)
        solution = Solution()

        # When
        actual = solution.is_symmetric(root)

        # Then
        expected = True
        self.assertEqual(actual, expected)

Strategy

Breadth First Search.

Explanation

The algorithm uses BFS. First, the algorithm pushes the left and right nodes of the root to the queue. Then, BFS traversal gets underway.

For each iteration, two nodes are popped from the queue. If one of the nodes is null, or the data of the two nodes doesn’t match, then the binary tree is asymmetrical. Otherwise, the children of the current two nodes is pushed to the queue.

In order for the binary tree to be symmetrical, the outer and inner children of the two current nodes must match. In other words, if l and r are the two current nodes of the left and right subtrees respectively, then l.left and r.right are the outer nodes and pushed to the queue consecutively, and then l.right and r.left are the inner nodes and pushed to the queue consecutively.

If traversal of the binary tree completes, then the binary tree is symmetrical.

Time Complexity

The algorithm visits every node of the binary tree once. Therefore, the time complexity of the algorithm is O(n).

Space Complexity

The algorithm pushes all nodes from a level of the binary tree to the queue before checking if any nodes from the same level match. In the case of a perfect binary tree, the number of nodes from a level doubles at each level. In other words, half the nodes in the binary tree are in the lowest level seen so far when viewing the levels of the binary tree from top to bottom. In other words, half the nodes in the binary tree are in the lowest level of the binary tree, which is proportional to n, where n is the number of nodes in the binary tree. Therefore, the auxiliary space complexity of the algorithm is O(n).

Links

data_structures_algorithms/algorithms/bfs/symmetric_tree at main ·…