Trees in Go: basic properties and computation

This is the second post in the series “Trees in Go”, where we explore the tree data structure and algorithms in the Go language. In the previous post, we introduced binary trees and showed their representation in Go, and how to instantiate them. In this post, we will introduce elementary properties of trees, and show how to compute them with simple algorithms.

Tree size: the number of nodes in the tree

There are many ways to define tree size. One way to define it is to say they are the number of nodes in the tree, that is the number of nodes that descend from the root, root included, that don’t have the value nil.

For instance, the following tree has size 5:

Tree with 5 nodes

When we say tree, it means the tree which has root the node with label 1 in that case.

We can also notice that the node labeled 2 is also the root of the subtree which contains the nodes 2, 4 and 5. This subtree is of size 3.

Compute the tree size

A lot of algorithms with trees are recursive. It simply means that to calculate a property p of the tree T, p(T), we can first calculate the same property on T.left and T.right. In the code it will look like this:

func computeProperty(node *TreeNode)…