Deep Dive into Binary, AVL, and Red-Black Trees with JavaScript

Implementing common operations on Binary Search Trees. Deep dive into self balancing BSTs - AVL and Red-Black Trees.

Jan 04, 2024

In this writing, we’ll dive into Binary Trees and Binary Search Trees, from their structure to code implementation. We’ll also explore self-balancing binary search trees like AVL or Red-Black trees.

Trees

A tree is a non-linear data structure, compared to linked lists, that consists of nodes connected by edges.

However, in coding challenges and interviews, you are more likely to encounter problems involving Binary Trees rather than general trees because of their simplicity.

Binary Trees

Structure of Binary Trees

Each node in a binary tree contains a value and pointers to two children, left and right, which refer to their left and right child nodes.

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

Node Relationships

Child and Parent Nodes: In the above example, 4 is the parent of 6 and 21 nodes; similarly, 6 and 21 are the child nodes of 4.
Siblings: 21 and 6 are siblings because they share the same parent, which is 4
Leaf and Root Nodes: The nodes that don’t have any children, like 1, 5, 2, 21, and 6, are called the Leaf Nodes, and the top node (7), which doesn’t have any parent, is called a root node.

Another useful tree property is the Tree Height — the length of the longest path from the root to a leaf.

Binary Search Tree (BST)

Binary Search Tree is a special type of Binary Tree that is in a sorted order:

Every node’s left subtree contains values less than the node’s value, and the right subtree contains values greater than the node’s value. This rule applies to every node (including the root) and their respective subtrees.

Operations and Their Big O Notations on BSTs

Access/Search

Accessing an element in BST is O(log n) for balanced trees, but it can be O(n) in the worst case — for unbalanced trees.

A tree is called Balanced when the height of the left and right subtrees of any node differ by no more than one. On the other hand, if the tree does not satisfy the balanced condition, it is called Unbalanced, which can lead to degraded performance in search operations.

We typically access or search for elements in BSTs using Recursion.

Start with the base case — if the root node is empty, return null
If the current node value is greater than the target value, go to the left
If the current node value is less than the target value, go to the right
Otherwise, that means that the current node value equals the target value — in this case, we return the current node

function searchBST(root, val) {
    if(!root) return null

    if(root.val > val) {
        return searchBST(root.left, val)
    } else if(root.val < val) {
        return searchBST(root.right, val)
    } else {
        return root
    }
};

Insertion

Insertion is O(log n) for balanced trees and O(n) for unbalanced trees, similar to searching.

Insertion also uses the Recursion technique to locate the correct spot for insertion; the main difference here is that once we find the spot where it needs to be inserted, we create a new TreeNode(val) and insert it in the tree.

function insertIntoBST(root, val) {
    if(!root) return new TreeNode(val)

    if(root.val > val) {
        root.left = insertIntoBST(root.left, val)
    } else if(root.val < val) {
        root.right = insertIntoBST(root.right, val)
    } 
    
    return root
};

Deletion

Deletion in a Binary Search Tree (BST) is a bit more complex than insertion or search, as it involves three different cases. Here’s a JavaScript function to handle deletion in a BST:

function deleteNode(root, value) {
    if(!root) return root

    // Find the node to be deleted
    if (value < root.value) {
        root.left = deleteNode(root.left, value)
    } else if (value > root.value) {
        root.right = deleteNode(root.right, value)
    } else {
        // Node with only one child or no child
        if (root.left == null) {
            return root.right
        } else if (root.right == null) {
            return root.left
        }

        // Node with two children: Get the inorder successor (smallest in the right subtree)
        root.value = minValue(root.right)

        // Delete the inorder successor
        root.right = deleteNode(root.right, root.value)
    }

    return root
}

This function covers the three cases of deleting a node in a BST:

Node with only one child or no child: Replace the node with its child or null if it has no children.
Node with two children: Find the inorder successor of the node (the smallest value in the right subtree), replace the node’s value with the inorder successor’s value, and then delete the inorder successor.
Searching for the node: If the node to be deleted is not found at the current level, the function recurses down the tree to the left or right child, depending on the value.

The time complexity of Deletion is O(log n) for balanced trees and O(n) for unbalanced trees in the worst case.

AVL Trees and Red-Black Trees

In production, we usually use Balanced Binary Search Trees like AVL Trees or Red-Black Trees.

These are two common types of self-balancing binary search trees.

AVL Tree

An AVL (Adelson-Velskii and Landis) tree is a self-balancing binary search tree.

It maintains a balance factor for each node, which is the difference between the heights of its left and right subtrees. If the balance factor exceeds a threshold, it performs rotations to restore balance.

The easiest way to understand how it works is by visualizing the common operations; the best resource for that is Visualgo AVL Tree playground.

So AVL trees ensure that the tree’s height remains logarithmic so that we can perform efficient searching, insertion, and deletion operations.

Red-Black Tree

A red-black tree is another type of self-balancing binary search tree.

It ensures that the tree is approximately balanced by using color properties (red or black) assigned to each node.

The red-black tree satisfies several properties, including ensuring that the longest path from the root to any leaf is no more than twice the length of the shortest path.

You can see in-depth how it works here — https://www.cs.usfca.edu/~galles/visualization/RedBlack.html.

Red-black trees are commonly used in computer science libraries and databases.

Both AVL and Red-Black trees keep the tree balanced all the time, preventing it from becoming a linear Linked List.

Hayk Simonyan | Substack

Hayk Simonyan