Articles / DSA · Part 23

Threaded Binary Trees, AVL Trees, and M-Way Search Trees

Explore Threaded Binary Trees, AVL Trees, and M-Way Search Trees. Understand threading, balance factors, rotations, and multi-key nodes with simple diagrams.

Threaded Binary Trees, AVL Trees, and M-Way Search Trees

In the previous article, we explored binary trees, their representations, and different traversal methods.

However, ordinary binary trees have some limitations. Traversing them may require extra memory for recursion or a stack, and an unbalanced search tree can become inefficient.

To address these challenges, computer science uses different types of trees.

In this article, we’ll explore three of them:

  1. Threaded Binary Trees
  2. AVL Trees
  3. M-Way Search Trees

1. Threaded Binary Trees

In an ordinary binary tree, some nodes do not have left or right children. Their corresponding pointers store NULL.

For example:

          20
         /  \
       10    30

Node 10 has no left or right child. Node 30 also has no children.

These empty pointers can be used more efficiently.

What Is a Threaded Binary Tree?

A Threaded Binary Tree is a binary tree in which otherwise-empty child pointers are used to connect nodes according to a traversal order.

Most commonly, these connections follow Inorder Traversal.

Let’s first recall the inorder traversal:

Left → Root → Right

For our example, the inorder sequence is:

10 → 20 → 30

In a threaded binary tree:

  • The empty right pointer of 10 can point to its inorder successor, 20.
  • The empty left pointer of 30 can point to its inorder predecessor, 20.
          20
         /  \
       10    30
         ───→
       ←────

The dashed connections represent threads, not ordinary child links.

These threads help us move to the next or previous node in the traversal order.

Types of Threaded Binary Trees

There are three common types:

A. Left-Threaded Binary Tree

Only empty left pointers are replaced with threads pointing to the inorder predecessor.

B. Right-Threaded Binary Tree

Only empty right pointers are replaced with threads pointing to the inorder successor.

C. Fully Threaded Binary Tree

Both empty left and right pointers can be replaced with threads.

Why Use Threaded Binary Trees?

  • They allow traversal without using recursion or an additional stack.
  • They make use of otherwise-empty pointers.
  • They provide convenient access to inorder predecessor and successor nodes.

However, insertion and deletion become more complicated because the threads must also be updated.

2. AVL Trees

Let’s understand another important problem with ordinary Binary Search Trees.

A Binary Search Tree (BST) follows this rule:

  • Values smaller than a node are placed in its left subtree.
  • Values greater than a node are placed in its right subtree.

But what happens when we insert values in sorted order?

Consider inserting:

10, 20, 30, 40

The resulting tree may look like this:

10
  \
   20
     \
      30
        \
         40

Instead of branching, the tree has become a chain.

Searching in such a tree can take O(n) time because we may need to visit every node.

To solve this problem, we use a self-balancing binary search tree called an AVL Tree.

What Is an AVL Tree?

An AVL Tree is a self-balancing Binary Search Tree in which the height difference between the left and right subtrees of every node can be at most 1.

This condition keeps the tree approximately balanced and prevents it from becoming a long chain.

What Is a Balance Factor?

The Balance Factor of a node is the difference between the heights of its left and right subtrees.

It is calculated as:

\[
BF = Height(Left) – Height(Right)
\]

In an AVL tree, every node must have a balance factor of:

\[
-1,\ 0,\ \text{or } +1
\]

Let’s understand:

  • 0: Both subtrees have equal heights.
  • +1: The left subtree is one level taller.
  • -1: The right subtree is one level taller.

If the balance factor becomes less than -1 or greater than +1, the tree needs rebalancing.

How Does an AVL Tree Maintain Balance?

An AVL tree uses a technique called Rotation to restore balance.

A Rotation is a local rearrangement of nodes that maintains the Binary Search Tree ordering while improving the tree’s balance.

There are four main cases:

A. Left-Left (LL) Case

This occurs when a node becomes unbalanced because a new value is inserted into the left subtree of its left child.

        30                 20
       /                  /  \
      20       →         10   30
     /
    10

A right rotation restores balance.

B. Right-Right (RR) Case

This occurs when a new value is inserted into the right subtree of the right child.

    10                       20
      \                     /  \
       20        →         10   30
         \
          30

A left rotation restores balance.

C. Left-Right (LR) Case

This occurs when a new value is inserted into the right subtree of the left child.

       30                 30                 20
      /                  /                  /  \
     10        →        20        →        10   30
       \               /
        20            10

It requires two rotations:

  1. Left rotation on the left child.
  2. Right rotation on the unbalanced node.

D. Right-Left (RL) Case

This occurs when a new value is inserted into the left subtree of the right child.

    10                 10                    20
      \                  \                  /  \
       30       →         20       →       10   30
      /                     \
     20                      30

It also requires two rotations:

  1. Right rotation on the right child.
  2. Left rotation on the unbalanced node.

Time Complexity of AVL Trees

Because AVL trees maintain their balance, their height remains O(log n).

Operation Time Complexity
Searching O(log n)
Insertion O(log n)
Deletion O(log n)

AVL trees are useful when we need efficient searching and want to keep the tree balanced.

3. M-Way Search Trees

So far, we’ve studied trees in which each node can have at most two children.

But what if a node could have more than two children and store multiple values?

This is the idea behind an M-Way Search Tree.

What Is an M-Way Search Tree?

An M-Way Search Tree is a search tree in which each node can have at most m children and at most m - 1 keys.

Here, m is called the Order of the tree.

For example:

  • A 2-way search tree can have at most 2 children and 1 key per node.
  • A 3-way search tree can have at most 3 children and 2 keys per node.
  • A 4-way search tree can have at most 4 children and 3 keys per node.

Understanding a 3-Way Search Tree

Consider this tree:

             [20 | 40]
             /   |   \
            /    |    \
       [10 | 15] [25 | 30] [50 | 60]

The root contains two keys: 20 and 40.

These keys divide the values into three ranges:

  • Left child: Values smaller than 20.
  • Middle child: Values greater than 20 but smaller than 40.
  • Right child: Values greater than 40.

For example, if we want to search for 30:

  1. Start at the root [20 | 40].
  2. Compare 30 with 20 and 40.
  3. Since 30 is between them, move to the middle child.
  4. Find 30 in [25 | 30].

This is how an M-Way Search Tree organises multiple keys within each node to guide searching.

Important Properties

An M-Way Search Tree follows these rules:

  1. Each node can have at most m children.
  2. Each node can contain at most m - 1 keys.
  3. Keys inside a node are stored in sorted order.
  4. The keys in different child subtrees fall within the ranges defined by the node’s keys.

Why Use M-Way Search Trees?

  • A node can store multiple keys.
  • A node can have more than two children.
  • A higher branching factor can reduce the number of levels needed for a given number of keys.
  • They form the foundation for advanced structures such as B-Trees and B+ Trees.

Important: An ordinary M-Way Search Tree is not necessarily balanced. Its height can still become large depending on how the keys are arranged.

4. Comparison of the Three Trees

Feature Threaded Binary Tree AVL Tree M-Way Search Tree
Main purpose Efficient traversal Maintain balance Store multiple keys per node
Children At most 2 At most 2 At most m
Special feature Uses threads Uses rotations Multiple keys per node
Main benefit Traversal without recursion or stack Efficient searching Higher branching factor

Conclusion

We explored three important tree structures:

  • Threaded Binary Trees: Use otherwise-empty pointers to make traversal easier.
  • AVL Trees: Maintain balance through rotations to support efficient searching, insertion, and deletion.
  • M-Way Search Trees: Store multiple keys in each node and allow more than two children.

Each structure addresses a different challenge in organising and accessing data.

In the next article, we’ll explore B-Trees and B+ Trees, which build on the idea of M-Way Search Trees and are widely used in database systems and file storage.


Further reading: GeeksforGeeks – Threaded Binary Tree · GeeksforGeeks – AVL Tree · e-PG Pathshala – Multi-Way Trees

Keep a copy

Read offline as a printout or PDF.

farhanpaal.com

Keep reading

DSA · Part 5

Arrays: Understanding the Basics

Learn the basics of arrays, including indexing, memory representation, accessing, updating, traversing, insertion, and deletion with simple C examples.

4 min read

Ask Farhan

Ask anything about Farhan