depth-first-search.md

Depth-First Search

Given the following Node struct and a slice of optional children nodes, implement a DepthFirstSearch method on Node that uses a depth-first search algorithm (navigating the tree from left to right) to return a slice of all the child node Name attributes in the appropriate order.

type Node struct {
	Name     string
	Children []*Node
}

For example, given the following tree:

      A
    / | \
   B  C  D
  / \   / \
 E   F G   H
    / \ \
   I  J  K

The resulting slice should be ["A", "B", "E", "F", "I", "J", "C", "D", "G", "K", "H"].

You may use the following test to exercise your solution.

depth-first-search_test.go

package search

import (
	"testing"

	"github.com/stretchr/testify/assert"
)

func TestDepthFirstSearch(t *testing.T) {
	cases := []struct {
		name     string
		input    *Node
		expected []string
	}{
		{
			name: "a",
			input: &Node{
				Name: "A",
				Children: []*Node{
					&Node{Name: "B"},
				},
			},
			expected: []string{"A", "B"},
		},
		{
			name: "b",
			input: &Node{
				Name: "A",
				Children: []*Node{
					&Node{Name: "B"},
					&Node{Name: "C"},
				},
			},
			expected: []string{"A", "B", "C"},
		},
		{
			name: "c",
			input: &Node{
				Name: "A",
				Children: []*Node{
					&Node{Name: "B", Children: []*Node{&Node{Name: "B1"}}},
					&Node{Name: "C", Children: []*Node{&Node{Name: "C1"}}},
					&Node{Name: "D", Children: []*Node{&Node{Name: "D1"}}},
				},
			},
			expected: []string{"A", "B", "B1", "C", "C1", "D", "D1"},
		},
		{
			name: "d",
			input: &Node{
				Name: "A",
				Children: []*Node{
					&Node{Name: "B", Children: []*Node{&Node{Name: "B1"}}},
					&Node{Name: "C", Children: []*Node{&Node{Name: "C1", Children: []*Node{&Node{Name: "CC1"}, &Node{Name: "CC2"}}}}},
					&Node{Name: "D", Children: []*Node{&Node{Name: "D1"}}},
				},
			},
			expected: []string{"A", "B", "B1", "C", "C1", "CC1", "CC2", "D", "D1"},
		},
	}

	for _, tc := range cases {
		t.Run(tc.name, func(t *testing.T) {
			assert.Equal(t, tc.expected, tc.input.DepthFirstSearch([]string{}))
		})
	}
}