Published on

# Data Structure: Tree

Authors

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:

`_10type Tree struct {_10 Value int_10 Left *Tree_10 Right *Tree_10}_10_10_10func NewTree(value int, left, right *Tree) *Tree {_10 return &Tree{value, left, right}_10}`

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:

`_8// create a new tree with value 10_8root := NewTree(10, nil, nil)_8_8// add a left child with value 5_8root.Left = NewTree(5, nil, nil)_8_8// add a right child with value 15_8root.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.

`_8func PreOrderTraversal(root *Tree) {_8 if root == nil {_8 return_8 }_8 fmt.Println(root.Value)_8 PreOrderTraversal(root.Left)_8 PreOrderTraversal(root.Right)_8}`

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.

main.go
tree
output
`_43package main_43_43import (_43 "fmt"_43)_43_43type Tree struct {_43 Val int_43 Left *Tree_43 Right *Tree_43}_43_43func NewTree(value int, left, right *Tree) *Tree {_43 return &Tree{value, left, right}_43}_43_43func PreOrderTraversal(root *Tree) []int {_43 if root == nil {_43 return nil_43 }_43_43 left := PreOrderTraversal(root.Left)_43 right := PreOrderTraversal(root.Right)_43_43 output := make([]int, 0)_43 output = append(output, root.Val)_43 output = append(output, left...)_43 output = append(output, right...)_43 return output_43_43}_43_43func main() {_43 root := NewTree(1, nil, nil)_43 root.Left = &Tree{Val: 2}_43 root.Left.Left = &Tree{Val: 4}_43 root.Right = &Tree{Val: 3}_43 root.Right.Left = &Tree{Val: 5}_43 root.Right.Right = &Tree{Val: 6}_43_43 output := PreOrderTraversal(root)_43 fmt.Println(output)_43}`

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.