Binary Tree Inversion

Question

I solved this problem.

Invert a binary tree.

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

To this

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

This problem looked a lot harder at first and then I was able to come up with a recursive solution to this.

/**
 * 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) || (root->left == NULL && root->right == NULL) )
 {
 return root;
 }
 TreeNode *temp = root->left;
 root->left = root->right;
 root->right = temp;
 invertTree(root->left);
 invertTree(root->right);
 return root;
 }
};

When I submitted this solution, I found that my submission ran faster than just 0.2 % of other submission for this problem.

Is there a better and faster approach to this, maybe an iterative one?

• 200_success: I would prefer to call it "mirroring". To me, "invert" sounds like flipping something upside-down.
• Jerry Coffin: @200_success: So think of it drawn with the root on the left instead of the top. :-)

Answer 1

It's hard to say exactly how much it'll affect execution speed, but your code isn't written how I'd write it.

First, I'd try to minimize the complexity of the initial condition. I'd only return if root was a null pointer. Unless the tree is tiny, you're probably going to gain more from a minimal test than from being able to skip a level of recursion.

Second, when you need to swap things, it's better to use swap to do the job. One of the interesting points of swap is that it's fairly common to specialize it, so you don't want to call std::swap directly. Rather, you typically want a using declaration to bring std::swap into scope, followed by a call to swap with an unqualified name, so if the namespace of the objects being swapped contains a swap, that'll be found via ADL, and otherwise lookup will fall back to std::swap.

using std::swap;
swap(root->left, root->right);
invertTree(left);
invertTree(right);

This may or may not improve speed for your particular case, but it certainly can in some cases (often enough that you usually want to follow this basic pattern for swapping items in C++).

• thebenman: Thanks. This looks much more cleaner and it ran better than around 43 % of other submission. It actually ran in 0 ms :)

Answer 2

I suspect the biggest slow down here is the if statement. Even if both left and right are NULL there is no harm in swapping them. The swap itself is likely quite fast, not much slower than the comparisons in the if. I think if you removed the comparisons you'd have almost double speed:

if ( root!=NULL ) {
 TreeNode* tmp = root->left;
 root->left = invertTree(root->right);
 root->right = invertTree(tmp);
}
return root;

• thebenman: I ran it with the if condition modification that you had suggested but there was no change in the execution time. But when I used std::swap instead it executed faster than 43 % of the other solution. I think major chuck of performance improvements comes from using std::swap.