Flip Binary Tree

Implement binaryTreeFlip(root) that returns the mirror image of a binary tree: every node keeps its value, but its left and right children are swapped, all the way down. This is the classic Invert Binary Tree problem. A node is a plain object { val, left, right }, and an empty tree (or a missing child) is null. Return a brand-new tree and leave the input untouched.

Signature

// A node is a plain object; an empty tree or missing child is null.
type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };

// root: the root of the tree to mirror (or null for an empty tree).
// returns: a NEW mirrored tree; the input is not mutated.
function binaryTreeFlip(root: TreeNode | null): TreeNode | null;

Examples

// A two-level tree: the children of the root swap sides.
//   1            1
//  / \    →     / \
// 2   3        3   2
binaryTreeFlip({
  val: 1,
  left: { val: 2, left: null, right: null },
  right: { val: 3, left: null, right: null },
});
// → { val: 1,
//     left:  { val: 3, left: null, right: null },
//     right: { val: 2, left: null, right: null } }

// A left-only child becomes a right-only child.
//   1          1
//  /     →      \
// 2              2
binaryTreeFlip({
  val: 1,
  left: { val: 2, left: null, right: null },
  right: null,
});
// → { val: 1, left: null, right: { val: 2, left: null, right: null } }

Notes

• Mirror every level. The swap is recursive — not just the root's two children, but every node's children, all the way to the leaves.
• Return a new tree. Build fresh nodes; do not reassign left/right on the nodes you were given. After the call, the original tree must be exactly as it was.
• Empty in, empty out. binaryTreeFlip(null) returns null, and any missing child stays null.
• Values are preserved. Only positions change — no node's val is altered, added, or dropped.
• Flipping twice is a no-op. Mirroring a mirror gives you back a tree equal to the original.