Two implementations are provided. Invert recurses and is the clearer of the two. InvertIterative uses an explicit stack, so its stack use is bounded regardless of tree height — the one to use when the input might be degenerate, since a tree built from sorted data has height n.

Install

go install github.com/zg/invbintree/cmd/invbintree@latest

Use

$ invbintree 4 2 6 1 3 5 7
7 6 5 4 3 2 1

$ echo "4,2,6,1,3,5,7" | invbintree -format level
4
6 2
7 5 3 1

Library

root := tree.FromSlice([]int{4, 2, 6, 1, 3, 5, 7})
root = tree.Invert(root)            // or tree.InvertIterative
fmt.Println(tree.InOrder(root))     // [7 6 5 4 3 2 1]

Correctness

Inversion is pinned by four properties rather than golden outputs alone:

a BST's in-order walk is ascending, so after inversion it must be descending
inverting twice is the identity
the recursive and iterative implementations agree on every input
the result satisfies the structural definition of a mirror (IsMirror)

The last three are checked against a few hundred randomly generated trees per run. A 200,000-node degenerate spine exercises the iterative version at a depth where recursion is the wrong tool.

go test ./...
go test -bench=. ./...