Introduction

In the previous article we covered Lists and their most common variations. Today we will continue with Trees, which are non-linear hierarchical structures used everywhere: file systems, databases, parsers, routing tables and even how some compilers represent code.

We will keep the same Container interface from the first article so all implementations stay consistent:

type Container interface {
  Empty() bool
  Size() int
  Clear()
  Values() []interface{}
  String() string
}

Trees

A Tree is a hierarchical data structure made of nodes connected by edges. Unlike Lists, where each element has at most one successor, in a Tree each node can have multiple children. There is one special node called the root at the top of the structure and from it the rest of the tree branches out.

Visually a tree looks like this:

         A
        / \
       B   C
      / \   \
     D   E   F

In this diagram A is the root, B and C are its children, and D, E, F are leaves (nodes without children).

Terminology

Before going through the variations, it helps to align on a few terms:

• Node: each element of the tree, holds a value and references to its children.
• Root: the topmost node of the tree.
• Parent / Child: a node directly connected above (parent) or below (child).
• Leaf: a node with no children.
• Depth: distance from the root to the node.
• Height: distance from the node to its deepest descendant leaf.
• Subtree: any node together with all its descendants.

Tree Traversals

There are a few common ways to visit every node of a tree. Using the example tree above:

         A
        / \
       B   C
      / \   \
     D   E   F

The four main traversals produce these orders:

• Pre-order (Root → Left → Right): A, B, D, E, C, F
• In-order (Left → Root → Right): D, B, E, A, C, F
• Post-order (Left → Right → Root): D, E, B, F, C, A
• Level-order / BFS (top to bottom, left to right): A, B, C, D, E, F

Pre/in/post-order are usually implemented with recursion, while level-order uses a queue.

Binary Trees

A Binary Tree is a tree where every node has at most two children, usually called Left and Right. It is the most common tree variation and the foundation for many others.

         5
        / \
       3   8
      / \   \
     1   4   9

A basic node and tree implementation in Go:

type BinaryTreeNode[V any] struct {
  Value V
  Left  *BinaryTreeNode[V]
  Right *BinaryTreeNode[V]
}

type BinaryTree struct {
  root *BinaryTreeNode[interface{}]
  size int
}

func (t *BinaryTree) Empty() bool {
  return t.size == 0
}

func (t *BinaryTree) Size() int {
  return t.size
}

func (t *BinaryTree) Clear() {
  t.root = nil
  t.size = 0
}

func (t *BinaryTree) Values() []interface{} {
  values := make([]interface{}, 0, t.size)
  inOrder(t.root, &values)
  return values
}

func (t *BinaryTree) String() string {
  return fmt.Sprintf("%v", t.Values())
}

func inOrder(n *BinaryTreeNode[interface{}], out *[]interface{}) {
  if n == nil {
    return
  }
  inOrder(n.Left, out)
  *out = append(*out, n.Value)
  inOrder(n.Right, out)
}

A plain Binary Tree imposes no ordering on values, so it is mostly useful as a base for other structures or when the hierarchy itself is what matters.

Binary Search Trees

A Binary Search Tree (BST) is a Binary Tree with one extra rule: for every node, all values in its left subtree are smaller, and all values in its right subtree are greater.

         8
        / \
       3   10
      / \    \
     1   6   14
        / \   /
       4   7 13

This invariant makes search, insertion and removal O(log n) on average, because at each step we cut the search space in half. The worst case (a fully unbalanced tree) degrades to O(n), which is exactly the problem AVL Trees solve.

A simple BST implementation in Go, reusing BinaryTreeNode[int] as the node type since the underlying structure is the same:

type BinarySearchTree struct {
  root *BinaryTreeNode[int]
  size int
}

func (t *BinarySearchTree) Insert(value int) {
  newRoot, inserted := insertBST(t.root, value)
  t.root = newRoot
  if inserted {
    t.size++
  }
}

func (t *BinarySearchTree) Contains(value int) bool {
  return searchBST(t.root, value) != nil
}

func (t *BinarySearchTree) Empty() bool {
  return t.size == 0
}

func (t *BinarySearchTree) Size() int {
  return t.size
}

func (t *BinarySearchTree) Clear() {
  t.root = nil
  t.size = 0
}

func (t *BinarySearchTree) Values() []interface{} {
  values := make([]interface{}, 0, t.size)
  bstInOrder(t.root, &values)
  return values
}

func (t *BinarySearchTree) String() string {
  return fmt.Sprintf("%v", t.Values())
}

func insertBST(n *BinaryTreeNode[int], value int) (*BinaryTreeNode[int], bool) {
  if n == nil {
    return &BinaryTreeNode[int]{Value: value}, true
  }
  if value < n.Value {
    newLeft, inserted := insertBST(n.Left, value)
    n.Left = newLeft
    return n, inserted
  }
  if value > n.Value {
    newRight, inserted := insertBST(n.Right, value)
    n.Right = newRight
    return n, inserted
  }
  return n, false
}

func searchBST(n *BinaryTreeNode[int], value int) *BinaryTreeNode[int] {
  if n == nil || n.Value == value {
    return n
  }
  if value < n.Value {
    return searchBST(n.Left, value)
  }
  return searchBST(n.Right, value)
}

func bstInOrder(n *BinaryTreeNode[int], out *[]interface{}) {
  if n == nil {
    return
  }
  bstInOrder(n.Left, out)
  *out = append(*out, n.Value)
  bstInOrder(n.Right, out)
}

The Insert method returns whether the value was actually inserted, which keeps size correct when duplicates are ignored.

The Values() method returns elements in sorted order for free, since an in-order traversal of a BST always produces a sorted sequence.

AVL Trees

The big problem with a plain BST is balance: if you insert sorted data, it degenerates into a linked list and lookups become O(n). AVL Trees fix this by keeping the tree balanced after every insertion or removal.

An AVL Tree is a BST where, for every node, the heights of the left and right subtrees differ by at most one. When this invariant breaks, the tree fixes itself using rotations.

A right rotation looks like this:

        y                   x
       / \                 / \
      x   T3      =>      T1  y
     / \                     / \
    T1  T2                  T2  T3

A basic AVL implementation in Go:

type AVLNode struct {
  Value  int
  Height int
  Left   *AVLNode
  Right  *AVLNode
}

type AVLTree struct {
  root *AVLNode
  size int
}

func (t *AVLTree) Insert(value int) {
  newRoot, inserted := insertAVL(t.root, value)
  t.root = newRoot
  if inserted {
    t.size++
  }
}

func (t *AVLTree) Empty() bool {
  return t.size == 0
}

func (t *AVLTree) Size() int {
  return t.size
}

func (t *AVLTree) Clear() {
  t.root = nil
  t.size = 0
}

func (t *AVLTree) Values() []interface{} {
  values := make([]interface{}, 0, t.size)
  avlInOrder(t.root, &values)
  return values
}

func (t *AVLTree) String() string {
  return fmt.Sprintf("%v", t.Values())
}

func avlHeight(n *AVLNode) int {
  if n == nil {
    return 0
  }
  return n.Height
}

func avlBalance(n *AVLNode) int {
  if n == nil {
    return 0
  }
  return avlHeight(n.Left) - avlHeight(n.Right)
}

func rotateRight(y *AVLNode) *AVLNode {
  x := y.Left
  t2 := x.Right
  x.Right = y
  y.Left = t2
  y.Height = 1 + max(avlHeight(y.Left), avlHeight(y.Right))
  x.Height = 1 + max(avlHeight(x.Left), avlHeight(x.Right))
  return x
}

func rotateLeft(x *AVLNode) *AVLNode {
  y := x.Right
  t2 := y.Left
  y.Left = x
  x.Right = t2
  x.Height = 1 + max(avlHeight(x.Left), avlHeight(x.Right))
  y.Height = 1 + max(avlHeight(y.Left), avlHeight(y.Right))
  return y
}

func insertAVL(node *AVLNode, value int) (*AVLNode, bool) {
  if node == nil {
    return &AVLNode{Value: value, Height: 1}, true
  }

  var inserted bool
  if value < node.Value {
    node.Left, inserted = insertAVL(node.Left, value)
  } else if value > node.Value {
    node.Right, inserted = insertAVL(node.Right, value)
  } else {
    return node, false
  }

  if !inserted {
    return node, false
  }

  node.Height = 1 + max(avlHeight(node.Left), avlHeight(node.Right))
  bf := avlBalance(node)

  if bf > 1 && value < node.Left.Value {
    return rotateRight(node), true
  }
  if bf < -1 && value > node.Right.Value {
    return rotateLeft(node), true
  }
  if bf > 1 && value > node.Left.Value {
    node.Left = rotateLeft(node.Left)
    return rotateRight(node), true
  }
  if bf < -1 && value < node.Right.Value {
    node.Right = rotateRight(node.Right)
    return rotateLeft(node), true
  }

  return node, true
}

func avlInOrder(n *AVLNode, out *[]interface{}) {
  if n == nil {
    return
  }
  avlInOrder(n.Left, out)
  *out = append(*out, n.Value)
  avlInOrder(n.Right, out)
}

The tree handles the four classic imbalance cases (LL, RR, LR, RL) and guarantees O(log n) operations even in the worst case.

Which one should you use?

There is no single best tree, the right pick depends on the problem:

• Binary Tree: useful as a generic base structure or when you need a hierarchical layout without ordering rules.
• Binary Search Tree: good when data tends to come in random order and average O(log n) operations are good enough.
• AVL Tree: better when you need guaranteed O(log n) lookups and the data may arrive sorted or in adversarial patterns.

Other variations like Red-Black Trees, B-Trees, Tries and Heaps each solve more specific problems, but they all build on the ideas covered here.

Conclusion

Today we covered Trees end-to-end: the core terminology, the four common traversals, and three important variations (Binary Trees, Binary Search Trees and AVL Trees) with implementations following the same Container interface from the previous article.

In the next article we will move on to another data structure category and keep using the same approach shown here.