1.3 KiB
1.3 KiB
invbintree
Invert a binary tree: swap the left and right child of every node, producing the mirror image.
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=. ./...