Trees
Trees are non-linear data structures used mainly for searching. Trees have maximum nodes of two children and a minimum of none. In trees, the property values of the left node are lesser than the property values of the right node. Nodes with no children are considered leaves.
Must-knows about trees
- A binary tree is a data structure where each node has 0, 1, or 2 sub-nodes.
- The root node is the first node of the tree, having no parents.
- An edge is the link from child to parent.
- The depth/height of the tree is the longest path from the root node to the furthest node.
- The depth of a node is the number of edges from the node to the root of the tree.
- A leaf is a node with no children.
- The children of the same parent are called siblings.
- Ancestors of a node are parent/grandparents to the parent of the node's parent.
- Trees are either balanced or unbalanced and balancing a tree is difficult and slow.
- The size of a tree is the number of descendants it has including itself.
Binary search tree
A tree is called a binary tree if it has a maximum of two child nodes. An empty tree
is also a valid binary tree. Binary trees have a root node with a left and a right subtree.
Binary search trees allow look-up operations, as well as addition, and removal of elements.
They store keys in a sorted order, to make look-up operations faster. Their space complexity is
of the order O(n), but their operations like insert, search, and delete are of the order O(log n).
Binary trees have the following properties:
- key of type
int
- value of type
int
- LeftNode of the node's type instance
- RightNode of the node's type instance
For example, the properties are arranged thus:
type TreeNode struct {
key int
value int
leftNode *TreeNode // best to put it first, as the orientation is left | value | right
rightNode *TreeNode
}
Binary tree operations
Operations possible with binary trees are grouped into two:
Basic Operations
- Inserting elements to a tree
- Deleting elements from a tree
- Searching for elements in a tree
- Traversing the tree
Auxiliary Operations
- Finding the size of a tree
- Finding the height of a tree
- Finding the level with the maximum sum
- Finding the least common ancestor (LCA) for a particular pair of nodes
- Others
Applications of binary trees
The following are examples of use-cases of binary trees:
- Expression trees for compilers
- Huffman coding trees for data compression algorithms
- Binary search trees (BST) for searching, inserting, and deleting in O(log n)
- Priority queues (PQ) for searching and deleting minimum or maximum values in O(log n) time.
Implementing binary trees in Go
Below is an example code where binary trees are implemented:
package main
import (
"fmt"
"math/rand"
"time"
)
// Tree type of recursive struct
type Tree struct {
Left *Tree
Value int
Right *Tree
}
// traverse method allows visiting of nodes with recursion
func traverse(t *Tree) {
if t == nil {
return
}
traverse(t.Left)
fmt.Print(t.Value, " ")
traverse(t.Right)
}
// create function populates the branches with random integers
func create(n int) *Tree {
var t *Tree
rand.Seed(time.Now().Unix())
for i := 0; i < 2*n; i++ {
temp := rand.Intn(n * 2)
t = insert(t, temp)
}
return t
}
// insert recursive function does lots of functions with each if statements
func insert(t *Tree, v int) *Tree {
if t == nil { // if the tree is empty
return &Tree{nil, v, nil}
}
if v == t.Value { // if the value exists in the tree
return t
}
if v < t.Value { // if the value should go left or right
t.Left = insert(t.Left, v)
}
t.Right = insert(t.Right, v)
return t
}
// main function
func main() {
tree := create(10)
fmt.Println("The root of the tree is ", tree.Value, " \n.")
traverse(tree)
// fmt.Println()
tree = insert(tree, -10)
tree = insert(tree, -2)
traverse(tree)
// fmt.Println()
fmt.Println(" \n The root of the tree is ", tree.Value)
}
Conclusion
This article teaches the reader about Trees and binary trees. The possible operations
with binary trees were also given, along with an implementation of some of these
operations.
In a future article, applications of binary trees in problem-solving with the Go
programming languages will be given.
Top comments (0)