Back to Repositories

Testing Binary Tree Traversal Algorithms in hello-algo

A comprehensive Go test suite that validates binary tree traversal algorithms and backtracking implementations in the hello-algo repository. The tests cover preorder traversal methods and path finding with specific node value conditions.

Test Coverage Overview

The test suite provides extensive coverage of binary tree operations and traversal algorithms.

Tests preorder traversal implementations with different constraints
Validates path finding between root and specific nodes
Covers node value filtering scenarios
Tests backtracking algorithm implementation

Implementation Analysis

The testing approach utilizes Go’s native testing framework with multiple test functions for different traversal scenarios.

Key patterns include:

Tree initialization using SliceToTree conversion
Path collection using slices of TreeNode pointers
Recursive traversal implementations
Backtracking template pattern implementation

Technical Details

Testing infrastructure includes:

Go testing package for unit test execution
Custom tree visualization utilities
Slice-based path tracking
Dynamic result collection using Go slices
Custom tree node structures from hello-algo package

Best Practices Demonstrated

The test suite exemplifies high-quality testing practices in Go.

Clear test case separation and organization
Comprehensive visualization of test data structures
Multiple validation approaches for the same concept
Proper memory management with pointer usage
Clean separation of test scenarios

krahets/hello-algo

zh-hant/codes/go/chapter_backtracking/preorder_traversal_test.go

            
// File: preorder_traversal_i_compact_test.go
// Created Time: 2023-05-09
// Author: Reanon ([email protected])

package chapter_backtracking

import (
	"fmt"
	"testing"

	. "github.com/krahets/hello-algo/pkg"
)

func TestPreorderTraversalICompact(t *testing.T) {
	/* 初始化二元樹 */
	root := SliceToTree([]any{1, 7, 3, 4, 5, 6, 7})
	fmt.Println("\n初始化二元樹")
	PrintTree(root)

	// 前序走訪
	res := make([]*TreeNode, 0)
	preOrderI(root, &res)

	fmt.Println("\n輸出所有值為 7 的節點")
	for _, node := range res {
		fmt.Printf("%v ", node.Val)
	}
	fmt.Println()
}

func TestPreorderTraversalIICompact(t *testing.T) {
	/* 初始化二元樹 */
	root := SliceToTree([]any{1, 7, 3, 4, 5, 6, 7})
	fmt.Println("\n初始化二元樹")
	PrintTree(root)

	// 前序走訪
	path := make([]*TreeNode, 0)
	res := make([][]*TreeNode, 0)
	preOrderII(root, &res, &path)

	fmt.Println("\n輸出所有根節點到節點 7 的路徑")
	for _, path := range res {
		for _, node := range path {
			fmt.Printf("%v ", node.Val)
		}
		fmt.Println()
	}
}

func TestPreorderTraversalIIICompact(t *testing.T) {
	/* 初始化二元樹 */
	root := SliceToTree([]any{1, 7, 3, 4, 5, 6, 7})
	fmt.Println("\n初始化二元樹")
	PrintTree(root)

	// 前序走訪
	path := make([]*TreeNode, 0)
	res := make([][]*TreeNode, 0)
	preOrderIII(root, &res, &path)

	fmt.Println("\n輸出所有根節點到節點 7 的路徑，路徑中不包含值為 3 的節點")
	for _, path := range res {
		for _, node := range path {
			fmt.Printf("%v ", node.Val)
		}
		fmt.Println()
	}
}

func TestPreorderTraversalIIITemplate(t *testing.T) {
	/* 初始化二元樹 */
	root := SliceToTree([]any{1, 7, 3, 4, 5, 6, 7})
	fmt.Println("\n初始化二元樹")
	PrintTree(root)

	// 回溯演算法
	res := make([][]*TreeNode, 0)
	state := make([]*TreeNode, 0)
	choices := make([]*TreeNode, 0)
	choices = append(choices, root)
	backtrackIII(&state, &choices, &res)

	fmt.Println("\n輸出所有根節點到節點 7 的路徑，路徑中不包含值為 3 的節點")
	for _, path := range res {
		for _, node := range path {
			fmt.Printf("%v ", node.Val)
		}
		fmt.Println()
	}
}