# Invert Binary Tree

• Approach #3
In order traversal of the given tree.
Store the traversed elements in a stack (or a array and reverse the array)
Build a binary tree with the midpoint approach with the above stack or reversed array

• @justanotherbring The key to note is tha inverted tree order is the reverse of the order traversal of of the existing tree .

• For the Iterative solution, we can use Stack also to store the children & swap their children. I wrote the below code in C#.

``````BinTreeNode InvertBinaryTreeIterative(BinTreeNode root)
{
if (root == null)
return null;

Stack<BinTreeNode> st = new Stack<BinTreeNode>();
st.Push(root);

while (st.Count > 0)
{
BinTreeNode node = st.Pop();
BinTreeNode temp = node.Left;
node.Left = node.Right;
node.Right = temp;

if (node.Left != null)
st.Push(node.Left);
if (node.Right != null)
st.Push(node.Right);
}

return root;
}
``````

• My shorter Java code:

``````public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}
}
``````

• I was doing this :

``````TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return NULL;
if (root -> left == NULL && root -> right == NULL) return root;

invertTree(root -> left);
invertTree(root -> right);

TreeNode *temp = root -> left;
root -> left = root -> right;
root -> right = root -> left;

return root;
}
``````

It's giving me runtime error. can anyone suggest what i am doing wrong?

• javascript

``````var invertTree = function(root) {
if (!root)
return null;

// recursive
invertTree(root.left);
invertTree(root.right);
temp = root.left;
root.left = root.right;
root.right = temp;

// iterative
// var queue = [];
// queue.unshift(root);
// while(queue[0]){
//     current = queue.pop();
//     temp = current.left;
//     current.left  = current.right;
//     current.right = temp;
//     if(current.left) queue.unshift(current.left);
//     if(current.right) queue.unshift(current.right);
// }

return root;
};
``````

• python:

``````Solution(object):
def invertTree(self, root):
if(root == None): return
root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
return root
``````

• go:

``````func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}
``````

• ``````const invertTree = root => root
? Object.assign(new TreeNode(root.val), {
left: invertTree(root.right),
right: invertTree(root.left)
})
: null
``````

• C

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

• ``````  public TreeNode InvertTree(TreeNode currentNode)
{
if (currentNode == null)
return null;

TreeNode rightNode = InvertTree(currentNode.right);
TreeNode leftNode = InvertTree(currentNode.left);

currentNode.left = rightNode;
currentNode.right = leftNode;

return currentNode;
}``````

• Conciseness of Python

``````        if root != None:
root.left, root.right = root.right, root.left
map(self.invertTree, (root.left, root.right))
return root
``````

Assuming Tree is presented similar to this

``````data Tree a = Empty | Node (Tree a) a (Tree a) deriving (...)

invertTree :: Tree a -> Tree a
invertTree Empty = Empty
invertTree (Node left n right) = Node (invertTree right) n (invertTree left)
``````

• Simple Recursion
public class Solution {
public TreeNode invertTree(TreeNode root) {

``````    if(root == null) return null;
TreeNode newR = root.left;
root.left = invertTree(root.right);
root.right = invertTree(newR);

return root;
}
``````

}

• @baila There is a simple mistake in the swap. Since you changed root->left, so root->right should be assigned to temp.

TreeNode *temp = root -> left;
root -> left = root -> right;
root -> right = temp;

Your solution is perfectly fine with this change.

• ``````             if (root == null){
return root;
}

TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;

invertTree(root.left);
invertTree(root.right);

return root;
``````

i think this is more eaiser to understand

• What if there is only one root without left of right node?Or only has right or only left tree?
May consider NullPointerException?

• sorry,forget what I've said..

• public TreeNode invertTree(TreeNode root) {
if (root != null){
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
}
return root;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.