Data Structures and C Programming



Data Structures Interview Questions

Pg : 1 , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14

AVL Tree

An AVL tree is a special type of binary tree that is always partially balanced. The criteria that is used to determine the level of balanced-ness is the difference between the heights of subtrees of a root in the tree. The height of tree is the number of levels in the tree. Or to be more formal, the height of a tree is defined as follows:

  1. The height of a tree with no elements is 0
  2. The height of a tree with 1 element is 1
  3. The height of a tree with > 1 element is equal to 1 + the height of its tallest subtree.
Height of a node
  • The height of a leaf is 1. The height of a null pointer is zero.
  • The height of an internal node is the maximum height of its children plus 1


 AVL trees are height-balanced binary search trees

Balance factor of a node

height(left subtree) - height(right subtree)

An AVL tree has balance factor calculated at every node

For every node, heights of left and right subtree can differ by no more than 1

Store current heights in each node


Animated AVL Tree


Notes on AVL Trees


AVL Tree Rotations Tutorial


AVL Tree C Program