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;
}

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

Last updated