Binary Tree Traversals in Go

When I first began my journey with Go I wanted to pick several simple and intuitive problems and code their solutions in Go. This not only helped me in mastering the language syntax and understanding the coding concepts specific to Go, but also was critical in developing the skills required to take the algorithms from their descriptive form to working solutions in Go.

One can find many such problems in Data Structures and Algorithms course. Websites such as Leetcode have hundreds of problems to test not only your algorithmic skills but coding skills. Here in this article, I will show how to perform binary tree traversals in Go starting with defining the necessary data structures for representing the tree nodes. I will also show different ways of performing such traversals — using recursion, using function closures and using iteration.

This is part 1 of the series — working with Binary Trees in Go.

• Part 1 Binary Tree Traversals in Go (this article)
• Part 2 Binary Tree Traversals in Go — using iteration (access it here)
• Part 3 Level order Traversal of Binary Trees in Go (access it here)
• Part4 Zigzag Level Order Traversal of Binary Trees in Go (access it here)
• Part 5 Right side View of a Binary Tree in Go
• Part 6 Binary Tree Serialization in Go

A binary tree T is defined recursively. It is defined as either empty or such that

• It has a special node called root node.
• T has two sets of nodes organized into left subtree and right subtree
• Both the left subtree and right subtrees themselves are binary trees

Every node in a binary tree has at most two children both of which can be empty or non-empty. How do we represent such a node in Go? It is fairly simple as shown below.

Representing a Binary Tree Node

Binary Tree Traversals

Traversing a binary tree is a common scenario when examining or manipulating the tree structure. We can make a choice during the traversal of a binary tree i.e., we can choose whether we want to visit the root first or the subtrees first. Such a choice leads to different traversal orders. The following three orders lead to three different traversals of a binary tree.

Inorder Traversal

• Visit or traverse the left subtree first
• Next, visit the root node
• Finally, visit the right subtree

Preorder Traversal

• Visit the root node first
• Next, visit the left subtree
• Finally, visit the right subtree

Postorder Traversal

• Visit the left subtree first
• Next, visit the right subtree
• Finally, visit the root node

As you can see the definitions are really simple and recursion makes it easy to code the traversal algorithms. In the following code I am printing all the node values in inorder fashion.

Inorder using recursion

I would also like to show how to use a function closure to collect all the node values in a slice and return it to the parent function. A function closure in Go is a function that is bound to a variable outside it’s scope i.e. it references a variable (or variables) that are outside its body. The following snippet just shows this.

Top-level inorder function that uses a function closure to process each node

InorderInternal function that recursively calls itself

Preorder and postorder functions can be coded similarly. The only change you will notice is the order in which nodes are visited.

Preorder traversal using recursion

Preorder traversal using Recursion

Preorder traversal using recursion and a function closure

Top-level preorder function that uses a function closure

A preorder internal function that calls itself

Postorder using recursion

Postorder traversal using recursion

Postorder using recursion and a function closure

Top-level postorder function that uses a closure

A postorder internal function that calls itself

I will show how to implement these traversal algorithms iteratively in part 2 of this series.