Invert a Binary Tree

Made popular by Max Howell in his 2015 Tweet, inverting a Binary Tree has became one of the must know algorithms. Google's reaction seems a bit excessive, but at least we know what they ask. Suppose we are given the following tree on the left. The inverted tree would be the one on the right. I will explore both the recursive and iterative solutions.

#       1                 1
#      / \               / \
#     9   8             8   9
#    / \   \           /   / \
#   6   4   3   -->   3   4   6
#  / \     /           \     / \
# 2   7   5             5   7   2
#
#  Regular tree in order: 2 6 7 9 4 1 8 5 3
# Inverted tree in order: 3 5 8 1 4 9 7 6 2

Recursive Approach

This implementation uses the pre-order depth first search traversal, but in-order traversal will work equally well. The base case is to terminate the recursive call when the current node is null. Otherwise, reverse the two children at each node then repeat the same process for the right subtree and the left subtree.

public static void invert(TreeNode root) {
    if (root == null)
        return;

    TreeNode temp = root.right;
    root.right = root.left;
    root.left = temp;

    invert(root.left);
    invert(root.right);
}

Iterative Approach

The implementation in this section also leverages depth first search, but from the iterative approach. Unlike the recursive implementation where the stack is managed by the system, the iterative implementation will instantiate a stack to hold the nodes at every level of the tree as it traverses down a branch. The two children are reversed at each node. Once the algorithm overshoots a leaf node, it will pop from the stack and works its way down the right side of the tree.

public static void invert(TreeNode root) {
    Stack<TreeNode> parents = new Stack<>();
    TreeNode cur = root;

    while(!parents.isEmpty() || cur != null) {
        if (cur != null) {
            TreeNode temp = cur.left;
            cur.left = cur.right;
            cur.right = temp;
            parents.push(cur);
            cur = cur.left;
        }
        else {
            TreeNode parent = parents.pop();
            cur = parent.right;
        }
    }
}

This article is my 36th oldest. It is 358 words long, and it’s got 0 comments for now.