Invert Binary Tree

Data Structures and Algorithms

Statement

Given the root node of a binary tree, transform the tree by swapping the left subtree and right subtree of each node. The result is a mirror image of the original tree. Return the root of the transformed tree.

Constraints

• 0 ≤ number of nodes ≤ 100
• -1000 ≤ node.values ≤ 1000

Solution

"""
production algorithm
"""


class Solution:
    def mirror_binary_tree(self, root):
        """
        time complexity O(n)
        space complexity O(n)
        """
        self.mirror_binary_tree_helper(root)
        return root

    def mirror_binary_tree_helper(self, root):
        """
        time complexity O(n)
        space complexity O(n)
        """
        if root is None:
            return
        root.left, root.right = root.right, root.left
        self.mirror_binary_tree_helper(root.left)
        self.mirror_binary_tree_helper(root.right)

"""
unit tests
"""

from unittest import TestCase
from algorithms.dfs.invert_binary_tree.solution import Solution
from data_structures.binary_tree.binary_tree import BinaryTreeNode


class SolutionTestCase(TestCase):
    def test_invert_binary_tree(self):
        # Given
        root = BinaryTreeNode(1)
        root.left = BinaryTreeNode(2)
        root.right = BinaryTreeNode(3)
        root.left.left = BinaryTreeNode(4)
        root.left.right = BinaryTreeNode(5)
        root.right.left = BinaryTreeNode(6)
        root.right.right = BinaryTreeNode(7)
        root.left.left.left = BinaryTreeNode(8)
        root.left.right.left = BinaryTreeNode(9)
        root.right.left.left = BinaryTreeNode(10)
        root.right.right.left = BinaryTreeNode(11)
        solution = Solution()

        # When
        result = solution.mirror_binary_tree(root)

        # Then
        self.assertEqual(result.data, 1)
        self.assertEqual(result.left.data, 3)
        self.assertEqual(result.right.data, 2)
        self.assertEqual(result.left.left.data, 7)
        self.assertEqual(result.left.right.data, 6)
        self.assertEqual(result.right.left.data, 5)
        self.assertEqual(result.right.right.data, 4)
        self.assertEqual(result.left.left.right.data, 11)
        self.assertEqual(result.left.right.right.data, 10)
        self.assertEqual(result.right.left.right.data, 9)
        self.assertEqual(result.right.right.right.data, 8)

Strategy

Depth First Search.

Explanation

The algorithm recurses from the root node of the tree. For each node, its left and right trees are swapped. In the end, the root of the transformed tree is returned.

Time Complexity

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

Space Complexity

The algorithm recurses to the bottom of the tree. The maximum depth of recursion is n, in the case of a degenerate tree. Therefore, the auxiliary space complexity of the tree is O(n).

Links

data_structures_algorithms/algorithms/dfs/invert_binary_tree at main ·…