Invert Binary Tree - Depth First Search / DFS on Tree

Problems
25

The return values of their “dfs” calls are being thrown away. They’re making temporary changes to left and right in the call stack, but not bubbling it up to the actual structure. It is being passed by value, not passed by reference.

26

what about this:

def invert_binary_tree(tree: Node) → Node:
current_node = tree
if current_node is None:
return
current_node.left, current_node.right = current_node.right, current_node.left
invert_binary_tree(current_node.left)
invert_binary_tree(current_node.right)
return current_node

27

The solution states that no additional states are carried other than the current tree that is being inverting. But the solution in Java creates a new Node object for each tree node, so essentially this is space complexity O(n). At the end of the execution, it ends up with 2 trees, the original and the inverted.

1 Like
29

Easy to understand solution:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def invert_binary_tree(tree: Node) -> Node:
    def dfs(node):
        if node:
            node.left, node.right = dfs(node.right), dfs(node.left) 
        return node
    return dfs(tree)
30

Without creating a new Node every time:

def invert(root: Node | None) -> Node | None:
    if root:
        root.left, root.right = invert(root.right), invert(root.left)
    return root

One-liner creating a new Node every time:

def invert(root: Node | None) -> Node | None:
    return Node(root.value, invert(root.right), invert(root.left)) if root else None
31

Simple Java solution

    public static Node<Integer> invertBinaryTree(Node<Integer> tree) {
        // If null then return 'null' node
        if(tree == null){
            return null;
        }
       //Swap left and right subtree
        Node leftTemp = tree.left;
        tree.left = tree.right;
        tree.right = leftTemp;
        
        //Recursive step to continue left then right, swapping subtree at each recursive call
        invertBinaryTree(tree.left);
        invertBinaryTree(tree.right);

        //Return the tree that you were given
        return tree;
    }
32

Here is an in-place implementation for JavaScript that uses array destructuring to flip the left and right nodes.

SPOILER: Click to view

function invertBinaryTree(tree) {
    if (tree === null) return tree; // A single node is the reverse of itself
    
    [tree.left, tree.right] = [tree.right, tree.left]; // Array destructuring flips left and right nodes

    // Checks if left or right is NOT null and calls the recursive function
    if (tree.left !== null) invertBinaryTree(tree.left);
    if (tree.right !== null) invertBinaryTree(tree.right);
    
    // Return the original tree modified in-place
    return tree;
}