# Data Structures Series V - Binary Trees  Subscribe to my newsletter and never miss my upcoming articles

Trees are non linear data structures in the world of computer science where each element is called a `node` and each `node` may or may not have children associated with them.

Binary Trees are a special type of trees where each node can have up to two children. Note: `node` in a tree might not have children, such `nodes` are called `leaf` nodes.

In this example we will implement the three most famous traversal algorithms and those are:

1. Pre Order Traversal : parent node gets printed first.

2. In Order Traversal : parent node gets printed in the middle.

3. Post Order Traversal : parent node gets printed last.

To note that if a child doesn't exists then it can simply be ignored with respect to the traversal algorithms.

Now, we have our `interface` defined with us.

``````type ITreeNode interface{
preOrder()
inOrder()
postOrder()
printValue()
}
``````

The next step to take is to define the struct which will implement the above interface, this struct will be a node of the tree.

``````type TreeNode struct {
val interface{}
left ITreeNode
right ITreeNode
}
``````

The field `val` can store any type as it is declared as an interface. The fields `left` and `right` are the two children nodes for a node of a binary tree. These fields can be `nil` as well when the specific child doesn't exists.

Now, we define the methods for the struct `TreeNode` which will make it implement the interface. To start with we have the `printValue()` method which simply prints the value being held by the tree node.

``````func (t *TreeNode) printValue() {
fmt.Print(t.val)
}
``````

Next we get to the traversal algorithms.

First, we have pre order traversal.

``````func (t *TreeNode) preOrder() {
t.printValue() // parent printed before the children
if t.left!=nil {
t.left.preOrder()
}
if t.right!=nil {
t.right.preOrder()
}
}
``````

Secondly, we define the in order traversal.

``````func (t *TreeNode) inOrder() {
if t.left!=nil {
t.left.preOrder()
}
t.printValue() // parent printed in between the children
if t.right!=nil {
t.right.preOrder()
}
}
``````

Lastly, we define the post order traversal.

``````func (t *TreeNode) postOrder() {
if t.left!=nil {
t.left.preOrder()
}
if t.right!=nil {
t.right.preOrder()
}
t.printValue() // parent printed after the children
}
``````

For running and trying out the above algorithms, we will define few more functions.

A constructor function to instantiate and return the pointer to the tree node.

``````func NewTreeNode(val interface{}, left ITreeNode, right ITreeNode) *TreeNode {
return &TreeNode{val: val, left: left, right: right}
}
``````

A function to create a small binary tree of three node.

``````func createTree() ITreeNode {
node1 := NewTreeNode(1,nil,nil) // leaf node with value 1
node2 := NewTreeNode(3,nil,nil) // leaf node with value 3
return NewTreeNode(2,node1, node2) // parent and root node with value 2
}
``````

To run the above written code.

``````    root := createTree()
/*
2
/   \
1       3
*/

root.preOrder()  // 2 -> 1 -> 3

root.postOrder() // 1 -> 3 -> 2

root.inOrder()   // 1 -> 2 -> 3
``````