invbintree/tree/tree_test.go

package tree

import (
	"math/rand"
	"reflect"
	"testing"
)

func TestInvert(t *testing.T) {
	tests := []struct {
		name string
		in   []int
		want []int // expected in-order after inversion
	}{
		{"empty", nil, []int{}},
		{"single", []int{1}, []int{1}},
		{"balanced", []int{4, 2, 6, 1, 3, 5, 7}, []int{7, 6, 5, 4, 3, 2, 1}},
		{"left degenerate", []int{5, 4, 3, 2, 1}, []int{5, 4, 3, 2, 1}},
		{"right degenerate", []int{1, 2, 3, 4, 5}, []int{5, 4, 3, 2, 1}},
		{"duplicates", []int{2, 2, 2}, []int{2, 2, 2}},
		{"negatives", []int{0, -5, 5, -10}, []int{5, 0, -5, -10}},
	}
	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			for _, impl := range []struct {
				name string
				fn   func(*Node) *Node
			}{{"recursive", Invert}, {"iterative", InvertIterative}} {
				t.Run(impl.name, func(t *testing.T) {
					got := InOrder(impl.fn(FromSlice(tt.in)))
					if !reflect.DeepEqual(got, tt.want) {
						t.Errorf("in-order after invert = %v, want %v", got, tt.want)
					}
				})
			}
		})
	}
}

// A BST's in-order walk is ascending; inverting must make it descending.
// This pins the actual meaning of the operation rather than a golden value.
func TestInvertReversesInOrder(t *testing.T) {
	rng := rand.New(rand.NewSource(1))
	for range 200 {
		vals := make([]int, rng.Intn(50))
		for i := range vals {
			vals[i] = rng.Intn(1000)
		}
		root := FromSlice(vals)
		before := InOrder(root)
		after := InOrder(Invert(root))

		if len(before) != len(after) {
			t.Fatalf("length changed: %d -> %d", len(before), len(after))
		}
		for i := range before {
			if before[i] != after[len(after)-1-i] {
				t.Fatalf("not reversed: %v -> %v", before, after)
			}
		}
	}
}

// Inverting twice is the identity. Any asymmetric bug shows up here even
// when the single-inversion output happens to look plausible.
func TestInvertIsInvolution(t *testing.T) {
	rng := rand.New(rand.NewSource(2))
	for range 200 {
		vals := make([]int, rng.Intn(40)+1)
		for i := range vals {
			vals[i] = rng.Intn(100)
		}
		orig := FromSlice(vals)
		ref := Clone(orig)
		if got := Invert(Invert(orig)); !Equal(got, ref) {
			t.Fatalf("double inversion changed the tree\nvals=%v", vals)
		}
	}
}

// The two implementations must agree on every input.
func TestImplementationsAgree(t *testing.T) {
	rng := rand.New(rand.NewSource(3))
	for range 300 {
		vals := make([]int, rng.Intn(60))
		for i := range vals {
			vals[i] = rng.Intn(500)
		}
		a, b := FromSlice(vals), FromSlice(vals)
		if !Equal(Invert(a), InvertIterative(b)) {
			t.Fatalf("recursive and iterative disagree\nvals=%v", vals)
		}
	}
}

// The result must satisfy the structural definition of a mirror.
func TestInvertProducesMirror(t *testing.T) {
	rng := rand.New(rand.NewSource(4))
	for range 200 {
		vals := make([]int, rng.Intn(40)+1)
		for i := range vals {
			vals[i] = rng.Intn(200)
		}
		orig := FromSlice(vals)
		ref := Clone(orig)
		if got := Invert(orig); !IsMirror(ref, got) {
			t.Fatalf("result is not the mirror of the input\nvals=%v", vals)
		}
	}
}

// Inversion must not lose, add or alter nodes.
func TestInvertPreservesShape(t *testing.T) {
	vals := []int{8, 3, 10, 1, 6, 14, 4, 7, 13}
	root := FromSlice(vals)
	wantSize, wantHeight := Size(root), Height(root)
	root = Invert(root)
	if got := Size(root); got != wantSize {
		t.Errorf("size = %d, want %d", got, wantSize)
	}
	if got := Height(root); got != wantHeight {
		t.Errorf("height = %d, want %d", got, wantHeight)
	}
}

// A degenerate tree is exactly where the recursive version would blow the
// stack, so the iterative one must handle a depth that proves the point.
func TestInvertIterativeDeepTree(t *testing.T) {
	const n = 200_000
	// Build the left spine directly. Going through Insert would be O(n^2),
	// which dominates the runtime without testing anything extra.
	root := New(n)
	cur := root
	for i := n - 1; i > 0; i-- {
		cur.Left = New(i)
		cur = cur.Left
	}
	if got := Height(root); got != n {
		t.Fatalf("setup: height = %d, want %d (tree is not degenerate)", got, n)
	}

	root = InvertIterative(root)

	if got := Size(root); got != n {
		t.Fatalf("size = %d, want %d", got, n)
	}
	// The left spine must now run right: every node keeps its value, but
	// the descent is through Right and Left is empty throughout.
	cur = root
	for i := n; i > 0; i-- {
		if cur == nil {
			t.Fatalf("spine ended early at depth %d", n-i)
		}
		if cur.Val != i {
			t.Fatalf("at depth %d: val = %d, want %d", n-i, cur.Val, i)
		}
		if cur.Left != nil {
			t.Fatalf("at depth %d: Left should be nil after mirroring a left spine", n-i)
		}
		cur = cur.Right
	}
	if cur != nil {
		t.Fatal("spine longer than expected")
	}
}

func TestTraversals(t *testing.T) {
	root := FromSlice([]int{4, 2, 6, 1, 3, 5, 7})
	if got, want := InOrder(root), []int{1, 2, 3, 4, 5, 6, 7}; !reflect.DeepEqual(got, want) {
		t.Errorf("InOrder = %v, want %v", got, want)
	}
	if got, want := PreOrder(root), []int{4, 2, 1, 3, 6, 5, 7}; !reflect.DeepEqual(got, want) {
		t.Errorf("PreOrder = %v, want %v", got, want)
	}
	want := [][]int{{4}, {2, 6}, {1, 3, 5, 7}}
	if got := LevelOrder(root); !reflect.DeepEqual(got, want) {
		t.Errorf("LevelOrder = %v, want %v", got, want)
	}
}

func TestNilSafety(t *testing.T) {
	if Invert(nil) != nil || InvertIterative(nil) != nil || Clone(nil) != nil {
		t.Error("operations on nil tree must return nil")
	}
	if Size(nil) != 0 || Height(nil) != 0 {
		t.Error("empty tree must have size and height 0")
	}
	if !Equal(nil, nil) || !IsMirror(nil, nil) {
		t.Error("nil trees are equal and mirrors of each other")
	}
	if Equal(nil, New(1)) || IsMirror(New(1), nil) {
		t.Error("nil must not compare equal to a non-empty tree")
	}
}

func BenchmarkInvert(b *testing.B) {
	vals := rand.New(rand.NewSource(5)).Perm(10_000)
	root := FromSlice(vals)
	b.ResetTimer()
	for b.Loop() {
		Invert(root)
	}
}

func BenchmarkInvertIterative(b *testing.B) {
	vals := rand.New(rand.NewSource(5)).Perm(10_000)
	root := FromSlice(vals)
	b.ResetTimer()
	for b.Loop() {
		InvertIterative(root)
	}
}