Trees in Go: definition and representation of binary trees

3 min readJan 19, 2019

This is the first post in the series “Trees in Go”, where we explore the tree data structure and algorithms in the Go language. In this post, we will introduce binary tree, and how to represent them. (link to skip to next post)

Binary trees

A binary tree is a recursive data structure. Essentially a binary can be nil or have 2 attributes, left and right that are both binary trees.

A struct in Go is a collection of fields. From the definition of binary tree, an immediate definition of the TreeNode struct is:

type TreeNode struct {
  Left  *TreeNode
  Right *TreeNode
}

We called the data structure recursive because in the definition of the TreeNode struct contains fields that are TreeNode themselves.

Instantiation

Graphically, a binary tree is usually represented by a branch to the left with a representation of the left tree and a branch to the right with a representation of the right tree. For instance, this is a representation of a binary tree:

Often, we omit all the branches to nil in order to simplify the representation of the binary tree:

We call leaf a binary tree whose left and right field are nil. We can instantiate a leaf in Go the following way:

func newLeaf() *TreeNode {
  return &TreeNode{nil, nil}
}

The short following program instantiate the tree we saw Fig 1 and 2 in Go:

func instantiateTree() *TreeNode {
  leftLeft := newLeaf()
  leftRight := newLeaf()
  left := &TreeNode{leftLeft, leftRight}
  right := newLeaf()
  root := &TreeNode{left, right}
  return root
}

Labeled binary trees

We can add data to each subtree of a Binary that is not null. Often, we add a field “value” to each node in the tree by defining the following ValuedTreeNode:

type ValuedTreeNode struct {
  Val   int
  Left  *ValuedTreeNode
  Right *ValuedTreeNode
}

Let’s assume we want to instantiate the following tree:

Then the following code would instantiate it:

func newValuedLeaf(val int) *ValuedTreeNode {
  return &ValuedTreeNode{val, nil, nil}
}

func instantiateValuedTree() *ValuedTreeNode {
  leftLeft := newValuedLeaf(4)
  leftRight := newValuedLeaf(5)
  left := &ValuedTreeNode{2, leftLeft, leftRight}
  right := newValuedLeaf(3)
  root := &ValuedTreeNode{1, left, right}
  return root
}

Summary

In this post, we looked at the definition of binary trees, and their representation in Go, as well as how to instantiate and add composite data in ValuedBinaryTree. Next time we will start to play with the basic properties of trees, and figure out how to compute them in Go.

Full code source

package main

/**
* Definition for a binary tree node.
*/
type TreeNode struct {
    Left  *TreeNode
    Right *TreeNode
}

/**
*  ValuedTreeNode is a TreeNode with a integer as composite data
*/
type ValuedTreeNode struct {
    Val   int
    Left  *ValuedTreeNode
    Right *ValuedTreeNode
}

func newLeaf() *TreeNode {
    return &TreeNode{nil, nil}
}

func newValuedLeaf(val int) *ValuedTreeNode {
    return &ValuedTreeNode{val, nil, nil}
}

func instantiateTree() *TreeNode {
    leftLeft := newLeaf()
    leftRight := newLeaf()
    left := &TreeNode{leftLeft, leftRight}
    right := newLeaf()
    root := &TreeNode{left, right}
    return root
}

func instantiateValuedTree() *ValuedTreeNode {
    leftLeft := newValuedLeaf(4)
    leftRight := newValuedLeaf(5)
    left := &ValuedTreeNode{2, leftLeft, leftRight}
    right := newValuedLeaf(3)
    root := &ValuedTreeNode{1, left, right}
    return root
}

func main() {
    instantiateTree()
    instantiateValuedTree()
}