54 lines
1.3 KiB
Markdown
54 lines
1.3 KiB
Markdown
# 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
|
|
|
|
```sh
|
|
go install github.com/zg/invbintree/cmd/invbintree@latest
|
|
```
|
|
|
|
## Use
|
|
|
|
```sh
|
|
$ 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
|
|
|
|
```go
|
|
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.
|
|
|
|
```sh
|
|
go test ./...
|
|
go test -bench=. ./...
|
|
```
|