How to insert an element into an AVL tree

An AVL (Adelson-Velskii and Landis) tree is practically a binary search tree with the requirement that, for every node in the tree, the height of the left and right subtrees can differ by at most 1. An AVL tree with just one node will have a height of 1, thus, an empty AVL tree will have a height of either -1 or 0.

The insertion and deletion operations for an AVL tree are, unfortunately, not as easy to understand or implement as the ones for a binary search tree. We add the new node to the AVL tree similarly, but then we have to balance the tree to meet the set requirement regarding heights. We perform rotation operations to balance the tree.

The four rotation operations, and thus our four programming goals for insertion, are:

  1. An insertion into the left subtree of the left child of the offending node.
  2. An insertion into the right subtree of the left child of the offending node.
  3. An insertion into the left subtree of the right child of the offending node.
  4. An insertion into the right subtree of the right child of the offending node.

Goals 1 and 4 are practically the same operation but mirrored. The same can be said for goals 2 and 3.

Boilerplate

Before moving on to the rest of the Answer, we should look at the two files in the widget below. We'll use the class templates in our implementation.

A glance at AVL.hpp shows that every node in our AVL tree will have a key, left and right nodes, and height. We also have a constructor that will set every new node's height to 1. We then have the AVL class. It has a constructor, destructor, and helper methods which are both necessary for the AVL tree to function and used later in our final main.cpp for testing purposes. We will only be discussing the methods listed below in line 37.

AVL.cpp
AVL.hpp
#include "AVL.cpp"
#ifndef __AVL_HPP
#define __AVL_HPP
// This struct acts as a node to be used in the AVL tree.
template <class T>
struct node{
    T key;
    node *left;
    node *right;
    int height;
    
    // This is the default constructor for the node.
    node (T key){
        this->key = key;
        left = NULL;
        right = NULL;
        height = 1;
    }
};
// The class for the AVL tree.
template <class T>
class AVL {
    node<T> *root;
    
public:
    // Required for the AVL tree to function.
    AVL();
    ~AVL();
    void postEmpty(node<T>* currNode);
    void deleteNode(node<T>* &currNode, T k);
    node<T>* FindMin(node<T>* currNode);
    node<T>* getRoot();
    
    // What we will implement.
    void insertNode(node<T>* &currNode, node<T>* newNode);
    int height (node<T>* p);
    int heightMax(node<T>* leftNode, node<T>* rightNode);
    void rotateLeft(node<T>* &currNode);
    void rotateRight(node<T>* &currNode);
    void doubleLeft(node<T>* &currNode);
    void doubleRight(node<T>* &currNode);
    void balance(node<T>* &currNode);
};
#endif

Solution

First of all, let's implement the basic insertion operation (same as the one for binary search trees).

template<class T>
void AVL<T>::insertNode(node<T>* &currNode, node<T>* newNode) {
   	if(currNode == NULL) {
		currNode = newNode;
	} else if(newNode->key < currNode->key) {
		insertNode(currNode->left, newNode);
	} else if(newNode->key > currNode->key) {
		insertNode(currNode->right, newNode);
	}
   	balance(currNode);
}

This is a fairly simple function:

  • There are two parameters. The first parameter is a reference to whatever node is supplied while the second parameter is simply the new node. The supplied node-reference is used for both setting the new node and for traversal.
  • Lines 3 and 4: Check to see whether there exists a node or not.
  • Lines 5 and 6: Traverse to the left of the node.
  • Lines 7 and 8: Traverse to the right of the node.
  • Line 10: The AVL magic begins, so let's start implementing the necessary rotation operations and the helper methods for height.

The height and heightMax function

Our balance and rotation methods are going to need to know the heights of nodes in order to actually check for them and decide on the rotation to be used. Luckily, we were making our nodes store values for height. Thankfully, getting the height of a node in an AVL tree is done the same way as in a binary search tree:

template <class T>
int AVL<T> :: height (node<T>* p) {
	int left = 0;
	int right = 0;
	if(p == NULL) {
		return 0;
	}
	left = height(p->left);
	right = height(p->right);
	if(left >= right) {
		// The plus-1 is due to the node
		// itself having a height of 1.
		return (left + 1);
	} else {
		return (right + 1);
	}
}

As we are going to be comparing the heights of nodes a lot, it is best to create a helper method to find the maximum height between two nodes:

template <class T>
int AVL<T>::heightMax(node<T>* leftNode, node<T>* rightNode) {
	if(height(leftNode) >= height(rightNode)) {
		return height(leftNode);
	} else if(height(leftNode) < height(rightNode)) {
		return height(rightNode);
	}
	return 0;
}

The balance method

With our helpers ready, let's make the balance method. In order to create the balance method, we must keep the above mentioned goals in mind. Those goals directly translate to which rotations have to be made and where.

template<class T>
void AVL<T>::balance(node<T>* &currNode) {
  	if(currNode == NULL) {
		return;
	}
  	if(height(currNode->left) - height(currNode->right) > 1) {
    	if(height(currNode->left->left) >= height(currNode->left->right)) {
			rotateRight(currNode);
		} else {
			doubleRight(currNode);
		}
  	} else if(height(currNode->right) - height(currNode->left) > 1) {
   		if(height(currNode->right->right) >= height(currNode->right->left)) {
			rotateLeft(currNode);
		} else {
			doubleLeft(currNode);
		}
  	}
  	currNode->height = heightMax(currNode->left, currNode->right) + 1;
}
  • Lines 3–5: simply check whether a node exists or not.
  • Lines 6–11: We keep goals 1 and 3 in mind. In line 6, we check for height difference between currNode's left and right nodes. If the difference is greater than 1 (can only be -1, 0, and 1), we go in and balance. We then check which type of left-rotation operation needs to be performed, on currNode, by applying the two goals as a condition.
  • Lines 12–18: We keep goals 2 and 4 in mind. In line 12, we check for height difference between currNode’s right and left nodes. If the difference is greater than 1 (can only be -1, 0, and 1), we go in and balance. We then check which type of right-rotation operation needs to be performed, on currNode, by applying the two goals as a condition.
  • Line 19: We then update the height of currNode using heightMax .

Note: The maximum height difference, thanks to the way both insertNode and balance work, will rarely ever be greater than 2. We always balance the tree at all places whenever we add a new node.

Rotations

We now just have our rotation operations left. We'll create the methods for left-rotation operations. Try a shot at right-rotation operations (or find them in the final section).

template<class T>
void AVL<T>::rotateLeft(node<T>* &currNode) {
   	node<T>* rightChild = currNode->right;
   	currNode->right = rightChild->left;
   	rightChild->left = currNode;
   	currNode->height = heightMax(currNode->left, currNode->right);
   	rightChild->height = heightMax(rightChild->right, currNode);
   	currNode = rightChild;
}

See the rotateLeft method in the illustration below:

rotateLeft in action
rotateLeft in action

To handle for goal three, we first right-rotate the right child (of the offending node) with its left child, and then left-rotate the parent node with the now new right child. Let's look at an illustration:

rotateLeft and rotateRight in action
rotateLeft and rotateRight in action

Hopefully, the diagram above made things easier to understand. We can take a shortcut with the double-left rotation like so:

template<class T>
void AVL<T>::doubleLeft(node<T>* &currNode) {
	rotateRight(currNode->right);
	rotateLeft(currNode);
}

Conclusion

Putting all of the newly created methods together into the AVL.cpp and creating a main.cpp for testing will result in the code block below. Feel free to play around with the code, especially main.cpp, to see whether AVL trees created by this implementation match your own.

main.cpp
AVL.cpp
AVL.hpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include "AVL.hpp"
using namespace std;
int values[25] = {55, 43, 26, 82, 93, 4, 39, 95, 50, 6, 62, 17, 21, 49, 77, 5, 32, 60, 88, 16, 44, 72, 80, 8, 36};
void test_addition()
{
	cout << "Testing Addition:\n";
	// Make an AVL tree that takes nodes
	// which have int values.
	AVL<int> Tree;
	node<int>* root = Tree.getRoot();
	// Populate the tree with nodes.
	for (int i = 0; i < 25; i++) {
		Tree.insertNode(root, new node<int>(values[i]));
	}
	// After tree is populated, check whether
	// the nodes are where they should belong.
	bool flag = false;
	if(root->key != 43) { flag = true; }
	if(root->right->key != 62) { flag = true; }
	if(root->left->key != 17) { flag = true; }
	if(root->left->left->left->key != 4) { flag = true; }
	if(root->left->right->right->key != 36) { flag = true; }
	if(root->right->left->right->key != 60) { flag = true; }
	if(root->right->right->right->right->key != 95) { flag = true; }
	if(root->left->left->right->left->key != 6) { flag = true; }
	if(flag) {
		cout << "Addition Test Failed!\n";
	} else {
		cout << "Addition Test Passed!\n";
	}
	cout << root->key << endl;
	cout << root->right->key << endl;
	cout << root->right->right->right->right->key << endl;
	cout << root->left->left->right->left->key << endl;
}
int main()
{
	test_addition();
}

Free AI Mock Interviews
Coding Interview
Coding PatternsFree Interview
Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.
System Design
You TubeFree Interview
Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Copyright ©2025 Educative, Inc. All rights reserved