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:
- 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:

# 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 :frowning: 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.
Fix it please.
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) {
if(tree == nullptr) return nullptr;

return tree;


void invert(Node* node)
if(node == nullptr) return;
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);

return tree;


Easy to understand

Node<int>* invertTree(Node<int>* root, Node<int>* left, Node<int>* right) {
    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) {
    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)
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) {
        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
        return root
    return dfs(root)