# Invert Binary Tree - Depth First Search / DFS on Tree

For the Python solution, thereâ€™s unnecessary creation of new Nodes. Instead, we can swap the existing nodes which is more memory efficient. What are others thoughts?

My solution is below for reference. Thanks!

def invert_binary_tree(tree: Node) â†’ Node:
â€śâ€ť"
Outline
- Postorder traversal O(log(h)) h = height of tree,
- O(log(n)) time if balanced
- AND O(n) time if skewed left/right
- Same for space O(log(n)) balanced && O(n) unbalanced (skewed)
â€śâ€ť"

# Empty node
if tree is None:
return

# tree = 1, tree.left = 3, tree.right = 2
# left = 2
# right = 3
# Post order traversal
left = invert_binary_tree(tree.left)
right = invert_binary_tree(tree.right)

# Swap the left and right child
tree.left,tree.right = right,left

return tree # 1

this site really sucks for c#. Starting to think I wasted my money The base â€śtry yourselfâ€ť doesnt compile

We are sorry and weâ€™ve fixed it.

Another good option for this problem, and perhaps the easiest to think about without any recursion, is doing a BFS with a Queue. Add the root to the queue to start, and then run a loop until the queue is empty. On each pass, if either of the children are not None or null or whatever your language uses, then add them to the queue. Swap the current nodeâ€™s children by simply pointing the left child node to the right child node and vice versa. The loop will then run until the whole tree is inverted.

Java Top down solution:

public static Node invertBinaryTree(Node tree) {

if(tree == null) return null;

Node temp = tree.right;
tree.right = tree.left;
tree.left = temp;

tree.left = invertBinaryTree(tree.left);
tree.right = invertBinaryTree(tree.right);

return tree;
}

The base C# code fails to compile. Can someone fix it please? Thanks.

Actually not, it is still an issue. And in Insert Into BST Iâ€™ve described by comment to Markâ€™s comment what is wrong.
Btw, resulted solution not in-place (as it stated in task) you create a new tree instead of retarget the links.

for C++:

Node* invert_binary_tree(Node* tree) {
// WRITE YOUR BRILLIANT CODE HERE
if(tree == nullptr) return nullptr;

invert(tree);
return tree;

}

void invert(Node* node)
{
if(node == nullptr) return;
invert(node->left);
invert(node->right);
std::swap(node->left, node->right);
}

sorry, Iâ€™m not sure why the code was formatted that way when I hit comment

You can change the line in Main â†’ System.out.println(String.join(" â€ś, res)); TO System.out.println(String.join(â€ť ", resArr));

You guys should seriously stop using C#, switch to C++ or a different OO language, C# is used so little nowadays, its not the 90s anymore

â€śYou guys should seriously stop using C++, switch to Rust, C++ is used so little nowadays, its not the 90s anymoreâ€ť

function invertBinaryTree(tree) {
if (tree === null) return null;

function dfs(node) {
[node.left, node.right] = [node.right, node.left];

if (node.left) dfs(node.left);
if (node.right) dfs(node.right);
}

dfs(tree);
return tree;

}

Easy to understand

Node<int>* invertTree(Node<int>* root, Node<int>* left, Node<int>* right) {
// WRITE YOUR BRILLIANT CODE HERE
Node<int>* leftTree = root->left;
Node<int>* rightTree = root->right;
if(leftTree != NULL) {
invertTree(leftTree, leftTree->left, leftTree->right);
}

if(rightTree != NULL) {
invertTree(rightTree, rightTree->left, rightTree->right);
}

root->left = rightTree;
root->right = leftTree;

return root;
}

Node<int>* invert_binary_tree(Node<int>* root) {
// WRITE YOUR BRILLIANT CODE HERE
if(root == NULL) return NULL;
return invertTree(root, root->left, root->right);
}

Can we please update with a discussion on Time and Space complexity for the solutions(rather than just stating it)?

I did this (Python) and it works. Is the solution creating an entirely new tree that is inverted or am i not understanding?
def invert_binary_tree(tree: Node) â†’ Node:
if not tree:
return tree
if not tree.left and not tree.right:
return tree
tree = swap_children(tree)
invert_binary_tree(tree.right)
invert_binary_tree(tree.left)
return tree

def swap_children(node):
temp = node.left
node.left = node.right
node.right = temp
return node

well guess I dont know how to format for this lol.

public static Node<Integer> invertBinaryTree(Node<Integer> tree) {
// WRITE YOUR BRILLIANT CODE HERE
if(tree == null) return null;
Node<Integer> temp = tree.left;
tree.left = invertBinaryTree(tree.right);
tree.right = invertBinaryTree(temp);
return tree;
}

So my following code works for the matching leetcode question #226, but doesnâ€™t work here??

def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(root):
if not root:
return None
temp = root.left
root.left = root.right
root.right = temp
dfs(root.left)
dfs(root.right)
return root
return dfs(root)