Computer Data structure: Binary Search Tree & AVL Tree

16 min readAug 29, 2025

Welcome to another article in our blog series on Computer Data Structures. In this article I will be discussing Binary Search Tree, and AVL (Aldelson-velsky and landis) Tree. Let’s get started.

Imbalance or Unbalanced Binary Tree

In the last article, we talked about balanced binary trees. We didn’t cover imbalanced trees, so let’s do that now.

An imbalance (or unbalanced) binary is simply the opposite of a balanced tree. In an imbalanced tree, the left and right subtrees of at least one node differ in height by more than one.

Self-balancing binary Search tree

In the part 6 of the blog post series, we gave some commonly used types of trees and in the list are some self-balancing binary search trees. I think we mentioned two, which are AVL and Red-Black Tree. We’re mentioning this because I will be discussing and implementing one of these mentioned self-balancing trees. So, what’s a self-balancing binary search tree?

A self-balancing binary search tree is a type of binary search tree that automatically adjusts its structure after insertion or deletion in order to control the height of the tree and to keep the tree as balanced as possible.

Note: The difference between a binary search tree and a self-balancing binary search tree is that while a binary search tree requires manual effort to keep the tree as balanced as possible, a self-balancing binary search tree achieves and maintains it balanced automatically through dynamic adjustments.

What is a Binary Search Tree?

Binary Search Tree is a type of Binary Tree in which Nodes are arranged in a specific order. The ordering properties of a Binary Search Tree are:

key of any parent node in a tree must be greater than the value of its left child node
key of any parent node in a tree must be less than the value of its right child node

With the above explanation and visual representation, you should understand the concept. In the following section we will discuss how binary search tree works, then we will implement a binary search tree using Go programming language.

How it Works

Binary search tree works by following a specific order known as the ordering properties of a binary search tree. above explain what they are. We will dive into how it works by using the below five numbers.

Numbers: 4, 5, 3, 20, 1.

The numbers will represent the key of each node that made up of the below binary search tree.

           4
         /   \
        3      5
       / \    / \ 
      1  nil nil 20

For example, let say you wants to organize the below number in a Binary Search Tree:

4, 5, 3, 20, 1.

[] — let say this box is our implementation of binary search tree that perform the organization of nodes on insertion following ordering properties of binary search tree

Note: A node is an element of a tree data structure. It contains a key and may have links (edges) to other nodes in the tree.

A simple Node look like this:  key
                               / \
                           LNode RNode

Here, LNode is the left child and RNode is the right child.

In a BST, when we insert a new node, we start from the root node.

If the new node’s key is less than the current node’s key, we go to the left child.
If the new node’s key is greater, we go to the right child.

Note: If the child position we want to insert into is empty, we place the new node there. If it’s already occupied, we move to that child node and repeat the comparison until we find an empty spot(i.e. nil).

Special case: If we are inserting a node with a key that already exists, we simply update that node’s value instead of creating a new node.

Performing Insertions in a Binary Search Tree

1. Insert 4  
 
      4
      /\      -   []
   nil  nil

We start with an empty tree, so the first node we insert (key 4) becomes the root node.

Since this is the first node, there’s nothing else to compare it to.
The left and right children are nil (pointing to nothing)

2. Insert 5 

      5 
     / \     -  []
   nil nil

Next, we insert a node with key 5:

Start at the root (4).
Compare 5 with 4: since 5 > 4, we move to the right child of 4.
The right child is nil, so we insert 5 there.

The tree now looks like this:

3. Insert 3

    3
   / \     -    []
 nil nil

Now we insert a node with key 3:

Start at the root (4).
Compare 3 with 4: since 3 < 4, we move to the left child of 4.
The left child is nil, so we insert 3 there.

The tree now looks like this:

                         4
                       /   \
                      3     5
                     /\    /  \
                  nil nil nil   nil

4. Insert 20  

   20
   /\      -   []
nil  nil

Next, we insert a node with key 20:

Start at the root (4).
Compare 20 with 4: since 20 > 4, move to the right child (5).
Compare 20 with 5: since 20 > 5, move to the right child of 5.
That position is nil, so we insert 20 there.

The tree now looks like this:

                                       4
                                     /   \
                                    3      5
                                   /\     / \ 
                                nil  nil nil  20
                                             / \
                                            nil  nil

5. Insert 1    

    1
   / \     -    []
nil  nil

Next, we insert a node with key 1:

Start at the root (4).
Compare 1 with 4: since 1 < 4, move to the left child (3).
Compare 1 with 3: since 1 < 3, move to the left child of 3.
The left child of 3 is nil, so we insert 1 there.

The tree now looks like this:

                                        4
                                     /     \
                                  3           5
                                /   \      /    \ 
                               1     nil  nil    20
                              /  \               / \
                           nil    nil          nil  nil

Above shows how binary search tree works, now let’s create a golang implementation of a binary search tree

Implementation

package main

// A rooted Tree
// Binary search Tree
import "fmt"
// define node
type Node struct {
    value     int
    leftNode  *Node
    rightNode *Node
}
func main() {
    // start Binary Search Tree
    // set the root node
    bst := NewBSTree(4)
    // Insert node into the tree
    bst.insertANode(5)
    bst.insertANode(3)
    bst.insertANode(20)
    bst.insertANode(1)
    bst.preOrderTraversal()
    fmt.Println()
    bst.inOrderTraversal()
    fmt.Println()
    bst.postOrderTraversal()
    fmt.Println()
}
func NewBSTree(rootNodeValue int) *Node {
    bst := &Node{value: rootNodeValue}
    return bst
}
func (bt *Node) insertANode(value int) {
    if value <= bt.value {
        if bt.leftNode != nil {
            bt.leftNode.insertANode(value)
            return
        } else {
            bt.leftNode = &Node{value: value}
            return
        }
    } else {
        if bt.rightNode != nil {
            bt.rightNode.insertANode(value)
            return
        } else {
            bt.rightNode = &Node{value: value}
            return
        }
    }
}
func (bt *Node) inOrderTraversal() {
    if bt == nil {
        return
    }
    bt.leftNode.inOrderTraversal()
    fmt.Printf("%d ", bt.value)
    bt.rightNode.inOrderTraversal()
}
func (bt *Node) preOrderTraversal() {
    if bt == nil {
        return
    }
    fmt.Printf("%d ", bt.value)
    bt.leftNode.preOrderTraversal()
    bt.rightNode.preOrderTraversal()
}
func (bt *Node) postOrderTraversal() {
    if bt == nil {
        return
    }
    bt.leftNode.preOrderTraversal()
    bt.rightNode.preOrderTraversal()
    fmt.Printf("%d ", bt.value)
}

What is an AVL Tree?

AVL Tree is a self-balancing Binary Search Tree. in which each node in the Tree maintains an additional piece of information known as balance factors, which are used to ensure that the tree remains balanced. Since AVL is a binary search tree, but self-balancing, let’s look into its difference with the binary search tree we just finished discussing above.

Difference between BST and AVL

The main difference between a binary search tree and AVL tree is balance. In regular BST, there is no guarantee of balance(i.e a tree could be imbalanced on operations such as insert and delete). For example, the tree can become skewed (like a linked list) if we insert elements in sorted order. E.g. insert node with the following keys [1], [2], [3], [4] respectively will result in the following structure:

Looking at the order you can see that it looks like a linked list,

                 1
                  \
                   2
                     \
                      3
                        \
                          4
This structure is essentially:
1 -> 2 -> 3 -> 4

Now, the problem with this is that operations like search, insert, delete take O(n) instead of O(log n) . and if we are to balance this, in order to improve the performance then we would have to do it manually.

But with AVL. our tree will never be imbalanced on operations such as insert, delete. because AVL implements a mechanism that ensures that the height difference between the left and right subtree of any node is at most 1 (i.e. it automatically balances the tree) and this keeps all operations such as insert and delete efficient with time complexity O(log n).

Get Mukailasam’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Let’s discuss how an AVL tree works. Then, we will implement one using the Go programming language.

How it Works

AVL tree works like BST but with an additional process that makes sure the tree is automatically balanced. This additional process is basically performing rotations when the balance factor is > 1 or < -1 after insertion or deletion.

So here are the rules.

Balance Factor

A balance factor in each node can be of three possible values and these values are:

1: balance factor= 0

2: balance factor= 1

3: balance factor = -1

A balance factor can be “0” or “1” or “-1”. If any node in the tree has another balance factor value besides these three values, i.e. balance factor is > 1 or < -1, that shows that the Tree is imbalanced, thus an automatic rotation operation will be done to restore the balance of the tree.

Note: that the values are integers and not strings or characters.

Let’s explain each of these balance factor values using below AVL tree structure.

The red curl bracket {} represent the nodes in the tree
The numbers in the square bracket [] with blue text color represent the balance factors in the tree. As you can see each node({}) in the above AVL tree structure has a balance factor.
The numbers in the node({}), the one with black text color represent the keys of the nodes

Now, let’s continue.

1: “0” -> The height of the right and left subtree are equal. This shows that the node and its subtrees are equal. E.g. Look at the above AVL tree structure, you will see that every node with the balance factor “0” has equal height by having no subtree . In the above structure all the nodes with the balance factor “0” have no subtree but if they are to have a subtree, the right and left subtree of each node with the balance factor “0” must be of the same height.

E.g.

The node with the key 200 has it right and left subtree height to be the same

2: “1” -> The height of the left subtree is one level higher than the right subtree. E.g. Looking at the above AVL tree structure, you will see that every node with the balance factor “1” has its left subtree height one level higher than its right subtree.

E.g.

3: “-1” -> The height of the right subtree is one level higher than the left subtree. E.g. Look at the above image of AVL tree, you will see that every node with the balance factor “-1” has its right subtree height one level higher than its left subtree.

E.g.

Imbalance & Rotation

There are four types of imbalances (i.e bf of a node in the tree is > 1 or < -1) in AVL tree and for each of these imbalances we have operations called rotations performed by an AVL tree to maintain its balance.

Note: for rotation to be done that means the balance factor of a node in the tree is > 1 or < -1 — imbalance

Imbalance — rotation

1: Right Right Imbalance — Left Rotation: Right Right imbalance happens when the right subtree of any node is two levels deeper than the left subtree, and this imbalance is specifically caused by the right child’s right subtree (i.e right right path). In order to fix this, a left rotation will be performed on the imbalance node. For example, when we insert nodes with the following keys [12], [14], [15] respectively, it will result in the following structure:

The above structure is imbalanced because the right subtree of the node with the key 12 is two levels deeper than its left subtree, which violates the AVL tree property.

H(RightSubtree(node[12])) = 2
H(LeftSubtree(node[12])) = 0
bf[node(12)] = H(LeftSubtree) — H(RightSubtree)
bf[node(12)] = 0–2
bf[node(12)] = -2
bf[node(12)] < -1, therefore rotation needs to be done.

In a normal BST, this structure remains imbalanced unless we manually rotate it. In an AVL tree, the rotation will happen automatically.

E.g.

Here the imbalance node is the node with key(12)
The imbalance node right child is the node with the key(14)

So the rotation goes like these:

It moves the imbalance node right child up to become the new root of the subtree.
The imbalanced node(key[12]) becomes the left child of its former right child node (key[14]).

Note: This restores balance when the heavier nodes are on the right right path

2: Left Left Imbalance — Right Rotation: Left Left imbalance happens when the left subtree of any node is two levels deeper than the right subtree, and this imbalance is specifically caused by the left child’s left subtree (i.e left left path). In order to fix this, a right rotation will be performed on the imbalance node. For example, when we insert nodes with the following keys [12], [10], [8] respectively, it will result in the following structure:

The above structure is imbalanced because the left subtree of the node with the key 12 is two levels deeper than its right subtree, which violates the AVL tree property.

H(RightSubtree(node[12])) = 0
H(LeftSubtree(node[12])) = 2
bf[node(12)] = H(LeftSubtree) — H(RightSubtree)
bf[node(12)] = 2–0
bf[node(12)] = 2
bf[node(12)] > 1, therefore rotation needs to be done.

In a normal BST, this structure remains imbalanced unless we manually rotate it. In an AVL tree, the rotation will happen automatically.

E.g.

Here the imbalance node is the node with key(12)
The imbalance node left child is the node with the key(10)

So the rotation goes like these:

It moves the imbalance node left child up to become the new root of the subtree.
The imbalanced node(key[12]) becomes the right child node of its former left child node(key[10]).

Note: This restores balance when the heavier nodes are on the left left path

3: Left Right Imbalance — Left Right Rotation: Left Right imbalance happens when the left subtree of any node is two levels deeper than the right subtree, and this imbalance is specifically caused by the left child’s right subtree (i.e. left right path). In order to fix this imbalance, a left rotation is first performed on the left child, followed by a right rotation on the node. For example, when we insert nodes with the following keys [12], [8], [10] respectively, it will result in the following structure:

The above structure is imbalanced because the height of the left subtree of the node with the key 12 is two levels deeper than its right subtree, and the imbalance is specifically due to the left child’s right subtree.

Imbalance node is the node with the key(12)
Imbalance node’s left child is the node with the key(8)
Left child’s right child is the node with the key(10)

1. Left Rotation on imbalance node’s left child i.e. node with the the key(8)

Node 10 moves up to become the new left child of 12.
Node 8 becomes the left child of 10.

2. Right Rotation on imbalance node i.e. node with the key(12)

Node 10 moves up to become the new root of the subtree.
Node 12 becomes the right child of 10.

4: Right Left Imbalance — Right Left Rotation: Right Left imbalance happens when the right subtree of any node is two levels deeper than the left subtree, and this imbalance is specifically caused by the right child’s left subtree (i.e. right left path). In order to fix this imbalance, a right rotation is first performed on the right child, followed by a left rotation on the node. For example, when we insert nodes with the following keys [12], [15], [14] respectively, it will result in the following structure:

The above structure is imbalanced because the height of the right subtree of the node with the key 12 is two levels deeper than its left subtree, and the imbalance is specifically due to the right child’s left subtree.

Imbalance node is the node with the key(12)
Imbalance node’s right child is the node with the key(15)
right child’s left child is the node with the key(14)

1. Right Rotation on imbalance node’s Right child i.e. node with the key(15)

Node 14 moves up to become the new right child of 12.
Node 15 becomes the right child of 14.

2. Left Rotation on imbalance node i.e. node with the key(12)

Node 14 moves up to become the new root of the subtree.
Node 12 becomes the Left child of 14.

Implementation

package main

import (
    "fmt"
)

// AVLTree structure. Public methods are Add, Remove, Update, Search, DisplayTreeInOrder.
type AVLTree struct {
    root *AVLNode
}

func main() {
    avlT := AVLTree{&AVLNode{key: 12, Value: "sam"}}
    avlT.Add(14, "Dan")
    avlT.Add(16, "Newt")
    fmt.Println(avlT.root.left)
}

func (n *AVLNode) displayNodesInOrder() {
    if n.left != nil {
        n.left.displayNodesInOrder()
    }
    fmt.Print(n.key, " ")
    if n.right != nil {
        n.right.displayNodesInOrder()
    }
}

func (t *AVLTree) Add(key int, value string) {
    t.root = t.root.add(key, value)
}

func (t *AVLTree) Remove(key int) {
    t.root = t.root.remove(key)
}

func (t *AVLTree) Update(oldKey int, newKey int, newValue string) {
    t.root = t.root.remove(oldKey)
    t.root = t.root.add(newKey, newValue)
}

func (t *AVLTree) Search(key int) (node *AVLNode) {
    return t.root.search(key)
}

func (t *AVLTree) DisplayInOrder() {
    t.root.displayNodesInOrder()
}

// AVLNode structure
type AVLNode struct {
    key   int
    Value string

    // height counts nodes (not edges)
    height int
    left   *AVLNode
    right  *AVLNode
}

// Adds a new node
func (n *AVLNode) add(key int, value string) *AVLNode {
    if n == nil {
        return &AVLNode{key, value, 1, nil, nil}
    }

    if key < n.key {
        n.left = n.left.add(key, value)
    } else if key > n.key {
        n.right = n.right.add(key, value)
    } else {
        // if same key exists update value
        n.Value = value
    }
    return n.rebalanceTree()
}

// Removes a node
func (n *AVLNode) remove(key int) *AVLNode {
    if n == nil {
        return nil
    }
    if key < n.key {
        n.left = n.left.remove(key)
    } else if key > n.key {
        n.right = n.right.remove(key)
    } else {
        if n.left != nil && n.right != nil {
            // node to delete found with both children;
            // replace values with smallest node of the right sub-tree
            rightMinNode := n.right.findSmallest()
            n.key = rightMinNode.key
            n.Value = rightMinNode.Value
            // delete smallest node that we replaced
            n.right = n.right.remove(rightMinNode.key)
        } else if n.left != nil {
            // node only has left child
            n = n.left
        } else if n.right != nil {
            // node only has right child
            n = n.right
        } else {
            // node has no children
            n = nil
            return n
        }

    }
    return n.rebalanceTree()
}

// Searches for a node
func (n *AVLNode) search(key int) *AVLNode {
    if n == nil {
        return nil
    }
    if key < n.key {
        return n.left.search(key)
    } else if key > n.key {
        return n.right.search(key)
    } else {
        return n
    }
}

// Displays nodes left-depth first (used for debugging)

func (n *AVLNode) getHeight() int {
    if n == nil {
        return 0
    }
    return n.height
}

func (n *AVLNode) recalculateHeight() {
    n.height = 1 + max(n.left.getHeight(), n.right.getHeight())
}

// Checks if node is balanced and rebalance
func (n *AVLNode) rebalanceTree() *AVLNode {
    if n == nil {
        return n
    }
    n.recalculateHeight()

    // check balance factor and rotateLeft if right-heavy and rotateRight if left-heavy
    balanceFactor := n.left.getHeight() - n.right.getHeight()
    if balanceFactor == -2 {
        // check if child is left-heavy and rotateRight first
        if n.right.left.getHeight() > n.right.right.getHeight() {
            n.right = n.right.rotateRight()
        }
        return n.rotateLeft()
    } else if balanceFactor == 2 {
        // check if child is right-heavy and rotateLeft first
        if n.left.right.getHeight() > n.left.left.getHeight() {
            n.left = n.left.rotateLeft()
        }
        return n.rotateRight()
    }
    return n
}

// Rotate nodes left to balance node
func (n *AVLNode) rotateLeft() *AVLNode {
    newRoot := n.right
    n.right = newRoot.left
    newRoot.left = n

    n.recalculateHeight()
    newRoot.recalculateHeight()
    return newRoot
}

// Rotate nodes right to balance node
func (n *AVLNode) rotateRight() *AVLNode {
    newRoot := n.left
    n.left = newRoot.right
    newRoot.right = n

    n.recalculateHeight()
    newRoot.recalculateHeight()
    return newRoot
}

// Finds the smallest child (based on the key) for the current node
func (n *AVLNode) findSmallest() *AVLNode {
    if n.left != nil {
        return n.left.findSmallest()
    } else {
        return n
    }
}

// Returns max number 
func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}