Data Structure: Tree

A tree is a non-linear data structure that consists of nodes organized in a hierarchical structure. Each node has a value, and a reference to one or more child nodes. The node at the top of the tree is called the root, and the nodes that don’t have any children are called leaf nodes.

Here is a simple example of how you can implement a tree data structure in Go:

type Tree struct {
	Value int
	Left  *Tree
	Right *Tree
}


func NewTree(value int, left, right *Tree) *Tree {
	return &Tree{value, left, right}
}

This implementation defines a Tree struct with three fields: Value, Left, and Right. The Value field holds the value of the node, and the Left and Right fields hold references to the left and right child nodes, respectively.

You can create a new tree by using the NewTree function, which takes a value and references to the left and right child nodes as arguments and returns a pointer to a new Tree struct.

Here’s an example of how you can use this tree data structure:

// create a new tree with value 10
root := NewTree(10, nil, nil)

// add a left child with value 5
root.Left = NewTree(5, nil, nil)

// add a right child with value 15
root.Right = NewTree(15, nil, nil)

This creates a tree with a root node that has a value of 10, and two child nodes with values of 5 and 15, respectively.

You can traverse the tree by starting at the root and visiting the child nodes in a specific order. For example, you can do a pre-order traversal by visiting the root node first, then the left child, and finally the right child.

func PreOrderTraversal(root *Tree) {
	if root == nil {
		return
	}
	fmt.Println(root.Value)
	PreOrderTraversal(root.Left)
	PreOrderTraversal(root.Right)
}

This function will print the values of the nodes in the tree in pre-order.

That example above only transverse and print the tree in pre-order. However, how if we need to get the data as an array ? For example, we have binary tree below.

package main

import (
	"fmt"
)

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

func NewTree(value int, left, right *Tree) *Tree {
	return &Tree{value, left, right}
}

func PreOrderTraversal(root *Tree) []int {
	if root == nil {
		return nil
	}

	left := PreOrderTraversal(root.Left)
	right := PreOrderTraversal(root.Right)

	output := make([]int, 0)
	output = append(output, root.Val)
	output = append(output, left...)
	output = append(output, right...)
	return output

}

func main() {
	root := NewTree(1, nil, nil)
	root.Left = &Tree{Val: 2}
	root.Left.Left = &Tree{Val: 4}
	root.Right = &Tree{Val: 3}
	root.Right.Left = &Tree{Val: 5}
	root.Right.Right = &Tree{Val: 6}

	output := PreOrderTraversal(root)
	fmt.Println(output)
}

     1
    / \
   /   \
  2     3
 /     / \
4     5   6

[4 2 1 5 3 6]

The only different we only save it to an array instead directly print to stdout. Try it yourself in go playground

There are many other ways you can use and manipulate tree data structures in Go, but this should give you a basic understanding of how they work. I will add more usecase in another post.