easyTrees & Binary Search Trees

Invert Binary Tree

Mirror a binary tree by swapping the left and right children of every node.

Work through the cases

3 examples

Input notation

A binary tree in level order on one line, using null for missing children. Omit trailing nulls; use null for an empty tree.

Expected result

The mirrored tree in the same level-order format.

Case 1

Input

4 2 7 1 3 6 9

Expected output

4 7 2 9 6 3 1

Case 2

Input

1 2

Expected output

1 null 2

Case 3

Input

null

Expected output

null

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Inverting a tree means swapping every node’s children and doing the same in both subtrees. One recursive walk is enough. Invert the two subtrees first, then swap the child pointers.

First, we check if root is null. If it is, we return null. Then, we recursively invert the left and right subtrees, set the inverted right subtree as the new left subtree, and set the inverted left subtree as the new right subtree. Finally, we return root.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode l = invertTree(root.left);
        TreeNode r = invertTree(root.right);
        root.left = r;
        root.right = l;
        return root;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.