Invert Binary Tree

NeetCode: Invert Binary Tree · LeetCode: 226. Invert Binary Tree · Difficulty: Easy

Given the root of a binary tree, invert it (swap the left and right child of every node) and return the root.

Example

Text

Input:      1            Output:     1
           / \                      / \
          2   3                    3   2
         / \                          / \
        4   5                        5   4

Trees are given in LeetCode's level-order array form: the root first, then each level from left to right, with null marking a missing node, so [1, 2, 3, 4, 5] is the tree above. The tree(Integer... values) helper in each program builds a TreeNode from such an array by filling children from a queue. TreeNode has the fields val, left, and right. A missing child is null: Java object references are nullable and the fields are mutable, so no wrapper type is needed.

Brute force: build a mirrored copy

Recursively create a new node for every original node, giving it the mirror image of the other subtree.

Java

import java.util.ArrayDeque;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode copy = new TreeNode(root.val);
        copy.left = invertTree(root.right);
        copy.right = invertTree(root.left);
        return copy;
    }
}

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    /** Preorder listing with N for a missing child. */
    static String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeInto(root, sb);
        return sb.toString();
    }

    static void serializeInto(TreeNode node, StringBuilder sb) {
        if (sb.length() > 0) sb.append(',');
        if (node == null) {
            sb.append('N');
            return;
        }
        sb.append(node.val);
        serializeInto(node.left, sb);
        serializeInto(node.right, sb);
    }

    public static void main(String[] args) {
        TreeNode root = tree(1, 2, 3, 4, 5);
        System.out.println(serialize(new Solution().invertTree(root)));
        System.out.println(serialize(new Solution().invertTree(null)));
    }
}

Output

1,3,N,N,2,5,N,N,4,N,N
N

The output is a preorder listing, with N for a missing child. The original tree is left unchanged. Time: O(n). Space: O(n) for the copy, plus O(h) recursion.

Optimal: swap the children in place

Invert both subtrees, then attach them swapped. No new nodes are allocated; the same TreeNode objects are reused and the original tree is modified. The code saves the old left child in a local variable before overwriting root.left.

Java

import java.util.ArrayDeque;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left = root.left;
        root.left = invertTree(root.right);
        root.right = invertTree(left);
        return root;
    }
}

public class Main {
    /** Builds a tree from LeetCode's level-order array, where null marks a missing node. */
    static TreeNode tree(Integer... values) {
        if (values.length == 0 || values[0] == null) return null;
        TreeNode root = new TreeNode(values[0]);
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int i = 1;
        while (!queue.isEmpty() && i < values.length) {
            TreeNode node = queue.poll();
            if (i < values.length && values[i] != null) {
                node.left = new TreeNode(values[i]);
                queue.add(node.left);
            }
            i++;
            if (i < values.length && values[i] != null) {
                node.right = new TreeNode(values[i]);
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }

    /** Preorder listing with N for a missing child. */
    static String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeInto(root, sb);
        return sb.toString();
    }

    static void serializeInto(TreeNode node, StringBuilder sb) {
        if (sb.length() > 0) sb.append(',');
        if (node == null) {
            sb.append('N');
            return;
        }
        sb.append(node.val);
        serializeInto(node.left, sb);
        serializeInto(node.right, sb);
    }

    public static void main(String[] args) {
        TreeNode root = tree(1, 2, 3, 4, 5);
        System.out.println(serialize(new Solution().invertTree(root)));
        System.out.println(serialize(new Solution().invertTree(null)));
    }
}

Output

1,3,N,N,2,5,N,N,4,N,N
N

Time: O(n). Space: O(h) for the recursion, where h is the height (O(log n) balanced, O(n) for a chain). A very deep chain can overflow the thread stack, which an explicit ArrayDeque stack avoids.