How to Invert a Binary Tree in C/C++?

This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

Invert a binary tree.
Example:

Input:

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

Output:

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

This is easy! I meant easy. Most tree-related algorithms such as traversal can be done using recursion, which is a straightforward approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) {
            return NULL; // terminal condition
        }
        auto left = invertTree(root->left); // invert left sub-tree
        auto right = invertTree(root->right); // invert right sub-tree
        root->left = right; // put right on left
        root->right = left; // put left on right
        return root;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == NULL) {
            return NULL; // terminal condition
        }
        auto left = invertTree(root->left); // invert left sub-tree
        auto right = invertTree(root->right); // invert right sub-tree
        root->left = right; // put right on left
        root->right = left; // put left on right
        return root;
    }
};

We need to recursively invert left and right sub-trees until they are NULL. Then we just need to swap the left and right sub-trees.

BTW, the ‘auto’ keyword in C++ is similar to the ‘var’ keyword in C#, which allows the compiler determine the best data-types for you.

See also other posts on inverting the binary tree:

• Teaching Kids Programming – Recursive Algorithm to Invert a Binary Tree
• How to Invert a Binary Tree in C/C++?
• Invert a Binary Tree using GoLang

–EOF (The Ultimate Computing & Technology Blog) —