Binary Tree Depth-First Search (DFS) Traversals in Go (GoLang).

binarytree-traversals-dfs.go

package binarytree

// Tree is a binary tree.
type Tree struct {
	Root *Node
}

// Node is a binary tree node.
type Node struct {
	Val   int
	Left  *Node
	Right *Node
}

// DFSPostorderTraversal uses Depth-First Search (DFS)
// to return the postorder traversal of the tree nodes.
func DFSPostorderTraversal(t *Tree) []int {
	sol := make([]int, 0)
	if t == nil || t.Root == nil {
		return sol
	}
	return postorderTraversal(t.Root, sol)
}

func postorderTraversal(n *Node, traversed []int) []int {
	if n == nil {
		return traversed
	}
	traversed = postorderTraversal(n.Left, traversed)
	traversed = postorderTraversal(n.Right, traversed)
	traversed = append(traversed, n.Val)
	return traversed
}

// DFSPreorderTraversal uses Depth-First Search (DFS)
// to return the preorder traversal of the tree nodes.
func DFSPreorderTraversal(t *Tree) []int {
	sol := make([]int, 0)
	if t == nil || t.Root == nil {
		return sol
	}
	return preorderTraversalWith(t.Root, sol)
}

func preorderTraversalWith(n *Node, traversed []int) []int {
	if n == nil {
		return traversed
	}
	traversed = append(traversed, n.Val)
	traversed = preorderTraversalWith(n.Left, traversed)
	traversed = preorderTraversalWith(n.Right, traversed)
	return traversed
}

// DFSInorderTraversal uses Depth-First Search (DFS)
// to return the inorder traversal of the tree nodes.
func DFSInorderTraversal(t *Tree) []int {
	sol := make([]int, 0)
	if t == nil || t.Root == nil {
		return sol
	}
	return inorderTraversal(t.Root, sol)
}

func inorderTraversal(n *Node, traversed []int) []int {
	if n == nil {
		return traversed
	}
	traversed = inorderTraversal(n.Left, traversed)
	traversed = append(traversed, n.Val)
	traversed = inorderTraversal(n.Right, traversed)
	return traversed
}

main.go

package binarytree

import "fmt"

// Here is an example
func main() {
	t := &Tree{
		Root: &Node{
			Val: 1,
			Left: &Node{
				Val: 2,
				Left: &Node{
					Val: 3,
				},
				Right: &Node{
					Val: 4,
				},
			},
			Right: &Node{
				Val: 5,
			},
		},
	}
	fmt.Println(DFSPostorderTraversal(t)) // [3 4 2 5 1]
	fmt.Println(DFSPreorderTraversal(t))  // [1 2 3 4 5]
	fmt.Println(DFSInorderTraversal(t))   // [3 2 4 1 5]
}

In main.go, we built this tree:

And here are the different traversals of this tree:

See "Binary Tree Breadth-First Search (BFS) Traversal using a queue in Go (GoLang)" HERE.