Invert a Binary Tree

This is a famous question that is often asked in coding interviews.

Given the following binary tree, swap the right and left nodes, so that the final result looks like this:

The head remains the same but every left node becomes a right node and vice versa.

Invert a Binary Tree - iterative solution

public TreeNode invert() {
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode current = stack.pop();
        TreeNode temp = current.left;
        current.left = current.right;
        current.right = temp;

        if (current.left != null) {
            stack.push(current.left);
        }

        if (current.right != null) {
            stack.push(current.right);
        }
    }

    return root;
}

Here, we are using a stack data structure to put the visited nodes in, so that we can pop them and invert.

Invert a Binary Tree - recursive solution

TreeNode invert(TreeNode node) {
    if (node == null)
        return node;

    /* do the subtrees */
    TreeNode left = invert(node.left);
    TreeNode right = invert(node.right);

    // swap the left and right pointers
    node.left = right;
    node.right = left;

    return node;
}

This is a more elegant solution, but the time and space complexities of both approaches are O(n). 
In an iterative way the space complexity is O(n) since we are creating a new data structure, and for the recursive way - the space complexity is also O(n) since there is a stack of method calls that is being created in the background.

That is all about how to invert a Binary Tree in Java.