Mirror of a Binary Tree

1. Problem Description

Given a binary tree, transform it into the mirror image of the original tree. Input description:

Definition of the mirror of a binary tree: original tree
    	    8
    	   /  \
    	  6   10
    	 / \  / \
    	5  7 9 11
    	Mirrored binary tree
    	    8
    	   /  \
    	  10   6
    	 / \  / \
    	11 9 7  5

2. Approach

• Swap the left and right nodes + preorder traversal
• Swap the left and right nodes + level-order traversal

3. Implementation

3.1. Preorder Traversal

• java

public class 二叉树的镜像
{
    public void Mirror(TreeNode root)
    {
        // Check whether the parameter is empty
        if (root == null)
        {
            return;
        }
        // Swap the left and right nodes
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // Apply the same operation to the left subtree
        this.Mirror(root.left);
        // Apply the same operation to the right subtree
        this.Mirror(root.right);
    }
}

• go

// Time complexity: O(n), where n is the number of tree nodes. Each node is traversed only once, so it is O(n)
// Space complexity: O(n), each node is stored once in the recursion stack
func Mirror3(pRoot *TreeNode) *TreeNode {
	if pRoot == nil {
		return nil
	}
	pRoot.Left, pRoot.Right = pRoot.Right, pRoot.Left
	Mirror(pRoot.Left)
	Mirror(pRoot.Right)

	return pRoot
}

3.2. Level-Order Traversal

• go

// Time complexity: O(n), where n is the number of tree nodes. Each node is traversed only once, so it is O(n)
// Space complexity: O(n)
func Mirror(pRoot *TreeNode) *TreeNode {
	if pRoot == nil {
		return nil
	}
	// Use a stack for preorder traversal
	stack := make([]*TreeNode, 0)
	stack = append(stack, pRoot)
	for len(stack) > 0 {
		removed := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		removed.Left, removed.Right = removed.Right, removed.Left
		if removed.Left != nil {
			stack = append(stack, removed.Left)
		}
		if removed.Right != nil {
			stack = append(stack, removed.Right)
		}
	}

	return pRoot
}


func Mirror2(pRoot *TreeNode) *TreeNode {
	if pRoot == nil {
		return nil
	}
	// Use a queue for level-order traversal
	queue := make([]*TreeNode, 0)
	queue = append(queue, pRoot)
	for len(queue) > 0 {
		removed := queue[0]
		queue = queue[1:]
		removed.Left, removed.Right = removed.Right, removed.Left
		if removed.Left != nil {
			queue = append(queue, removed.Left)
		}
		if removed.Right != nil {
			queue = append(queue, removed.Right)
		}
	}

	return pRoot
}

4. References

• Mirror of a Binary Tree - NowCoder
• Invert Binary Tree - LeetCode