226 Invert Binary Tree

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to
     4
   /   \
  7     2
 / \   / \
9   6 3   1

void swap(TreeNode *&a, TreeNode *&b) {
    TreeNode *temp = a;
    a = b;
    b = temp;
}

TreeNode* invertTree(TreeNode* root) {
    if (!root) return NULL;

    queue<TreeNode*> q;
    q.push(root);

    while(!q.empty())
    {
        TreeNode* node = q.front();
        q.pop();

        swap(node->left, node->right);

        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return root;
}

The Idea: Follow a level order traversal and swap left and right child nodes. Consider the tree with just a left and right child. The solution would be to simple swap the children. Note that we are swapping the addresses, and not the values of the nodes. This ensure that the entirety of the left side of the tree becomes the right side of the tree all together. In otherwords, we are swapping subtrees.

Complexity: O(n) time and space

DFS Approach

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;

    TreeNode *temp = root->left;
    root->left = invertTree(root->right);
    root->right = invertTree(temp);
    return root;

}

• The idea is the same (we perform a swap on each child for each parent node. In the end, we have to be comfortable with three things. The first, is that we create N temporary Nodes, each of which have their unique local stack frame. Secondly, we move down the trees right child continuously until we hit null. So the first real swap will be a swap of nullptrs. However, when we return twice, the root will be 2 and root->left will have access to root->right, and vise-versa because of the temporary variable.

Python Solution

import queue


class Solution:
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """

        q = queue.Queue()
        if root:
            q.put(root)

        while not q.empty():
            front = q.get()
            front.left, front.right = front.right, front.left
            if front.left:
                q.put(front.left)
            if front.right:
                q.put(front.right)

        return root