Data Structures Series V - Binary Trees

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