Category: Data Structures

AVL Tree Properties | Problems on AVL Tree

AVL Tree-

 

Before you go through this article, make sure that you have gone through the previous article on AVL Trees.

 

We have discussed-

  • AVL trees are self-balancing binary search trees.
  • In AVL trees, balancing factor of each node is either 0 or 1 or -1.

 

In this article, we will discuss AVL Tree Properties.

 

AVL Tree Properties-

 

Important properties of AVL tree are-

 

Property-01:

 

Maximum possible number of nodes in AVL tree of height H

= 2H+1 – 1

 

Example-

 

Maximum possible number of nodes in AVL tree of height-3

= 23+1 – 1

= 16 – 1

= 15

Thus, in AVL tree of height-3, maximum number of nodes that can be inserted = 15.

 

 

We can not insert more number of nodes in this AVL tree.

 

Property-02:

 

Minimum number of nodes in AVL Tree of height H is given by a recursive relation-

N(H) = N(H-1) + N(H-2) + 1

 

Base conditions for this recursive relation are-

  • N(0) = 1
  • N(1) = 2

 

Example-

 

Minimum possible number of nodes in AVL tree of height-3 = 7

 

 

(For explanation, Refer problem-01)

 

Property-03:

 

Minimum possible height of AVL Tree using N nodes

= ⌊log2N⌋

 

Example-

 

Minimum possible height of AVL Tree using 8 nodes

= ⌊log28⌋

= ⌊log223

= ⌊3log22⌋

= ⌊3⌋

= 3

 

Property-04:

 

Maximum height of AVL Tree using N nodes is calculated using recursive relation-

N(H) = N(H-1) + N(H-2) + 1

 

Base conditions for this recursive relation are-

  • N(0) = 1
  • N(1) = 2

 

NOTE-

 

  • If there are n nodes in AVL Tree, its maximum height can not exceed 1.44log2n.
  • In other words, Worst case height of AVL Tree with n nodes = 1.44log2n.

 

PRACTICE PROBLEMS BASED ON AVL TREE PROPERTIES-

 

Problem-01:

 

Find the minimum number of nodes required to construct AVL Tree of height = 3.

 

Solution-

 

We know, minimum number of nodes in AVL tree of height H is given by a recursive relation-

 

N(H) = N(H-1) + N(H-2) + 1

 

where N(0) = 1 and N(1) = 2

 

Step-01:

 

Substituting H = 3 in the recursive relation, we get-

N(3) = N(3-1) + N(3-2) + 1

N(3) = N(2) + N(1) + 1

N(3) = N(2) + 2 + 1                (Using base condition)

N(3) = N(2) + 3                      …………(1)

 

To solve this recursive relation, we need the value of N(2).

 

Step-02:

 

Substituting H = 2 in the recursive relation, we get-

N(2) = N(2-1) + N(2-2) + 1

N(2) = N(1) + N(0) + 1

N(2) = 2 + 1 + 1                 (Using base conditions)

∴ N(2) = 4                          …………(2)

 

Step-03:

 

Using (2) in (1), we get-

N(3) = 4 + 3

∴ N(3) = 7

Thus, minimum number of nodes required to construct AVL tree of height-3 = 7.

 

Problem-02:

 

Find the minimum number of nodes required to construct AVL Tree of height = 4.

 

Solution-

 

We know, minimum number of nodes in AVL tree of height H is given by a recursive relation-

 

N(H) = N(H-1) + N(H-2) + 1

 

where N(0) = 1 and N(1) = 2

 

Step-01:

 

Substituting H = 4 in the recursive relation, we get-

N(4) = N(4-1) + N(4-2) + 1

N(4) = N(3) + N(2) + 1               …………(1)

 

To solve this recursive relation, we need the value of N(2) and N(3).

 

Step-02:

 

Substituting H = 2 in the recursive relation, we get-

N(2) = N(2-1) + N(2-2) + 1

N(2) = N(1) + N(0) + 1

N(2) = 2 + 1 + 1                 (Using base conditions)

∴ N(2) = 4                          …………(2)

 

Step-03:

 

Substituting H = 3 in the recursive relation, we get-

N(3) = N(3-1) + N(3-2) + 1

N(3) = N(2) + N(1) + 1

N(3) = 4 + 2 + 1                 (Using (2) and base condition)

∴ N(3) = 7                          …………(3)

 

Step-04:

 

Using (2) and (3) in (1), we get-

N(4) = 7 + 4 + 1

∴ N(4) = 12

Thus, minimum number of nodes required to construct AVL tree of height-4 = 12.

 

Problem-03:

 

What is the maximum height of any AVL tree with 10 nodes?

 

Solution-

 

For calculating the maximum height of AVL tree with n nodes, we use a recursive relation-

 

N(H) = N(H-1) + N(H-2) + 1

 

Step-01:

 

Substituting H = 2 in the recursive relation, we get-

N(2) = N(2-1) + N(2-2) + 1

N(2) = N(1) + N(0) + 1

N(2) = 2 + 1 + 1                (Using base conditions)

∴ N(2) = 4                          …………(1)

 

So, minimum number of nodes required to construct AVL tree of height-2 = 4.

 

Step-02:

 

Substituting H = 3 in the recursive relation, we get-

N(3) = N(3-1) + N(3-2) + 1

N(3) = N(2) + N(1) + 1

N(3) = 4 + 2 + 1                (Using (1) and base condition)

∴ N(3) = 7                          …………(2)

 

So, minimum number of nodes required to construct AVL tree of height-3 = 7.

 

Step-03:

 

Substituting H = 4 in the recursive relation, we get-

N(4) = N(4-1) + N(4-2) + 1

N(4) = N(3) + N(2) + 1

N(4) = 7 + 4 + 1                (Using (1) and (2))

∴ N(4) = 12

 

So, minimum number of nodes required to construct AVL tree of height-4 = 12.

 

But given number of nodes = 10 which is less than 12.

Thus, maximum height of AVL tree that can be obtained using 10 nodes = 3.

 

Problem-04:

 

What is the maximum height of any AVL tree with 77 nodes?

 

Solution-

 

For calculating the maximum height of AVL tree with n nodes, we use a recursive relation-

 

N(H) = N(H-1) + N(H-2) + 1

 

Step-01:

 

Substituting H = 2 in the recursive relation, we get-

N(2) = N(2-1) + N(2-2) + 1

N(2) = N(1) + N(0) + 1

N(2) = 2 + 1 + 1                (Using base conditions)

∴ N(2) = 4                          …………(1)

 

So, minimum number of nodes required to construct AVL tree of height-2 = 4.

 

Step-02:

 

Substituting H = 3 in the recursive relation, we get-

N(3) = N(3-1) + N(3-2) + 1

N(3) = N(2) + N(1) + 1

N(3) = 4 + 2 + 1                (Using (1) and base condition)

∴ N(3) = 7                          …………(2)

 

So, minimum number of nodes required to construct AVL tree of height-3 = 7.

 

Step-03:

 

Substituting H = 4 in the recursive relation, we get-

N(4) = N(4-1) + N(4-2) + 1

N(4) = N(3) + N(2) + 1

N(4) = 7 + 4 + 1                (Using (1) and (2))

∴ N(4) = 12                        …………(3)

 

So, minimum number of nodes required to construct AVL tree of height-4 = 12.

 

Step-04:

 

Substituting H = 5 in the recursive relation, we get-

N(5) = N(5-1) + N(5-2) + 1

N(5) = N(4) + N(3) + 1

N(5) = 12 + 7 + 1                (Using (2) and (3))

∴ N(5) = 20                          …………(4)

 

So, minimum number of nodes required to construct AVL tree of height-5 = 20.

 

Step-05:

 

Substituting H = 6 in the recursive relation, we get-

N(6) = N(6-1) + N(6-2) + 1

N(6) = N(5) + N(4) + 1

N(6) = 20 + 12 + 1                (Using (3) and (4))

∴ N(6) = 33                            …………(5)

 

So, minimum number of nodes required to construct AVL tree of height-6 = 33.

 

Step-06:

 

Substituting H = 7 in the recursive relation, we get-

N(7) = N(7-1) + N(7-2) + 1

N(7) = N(6) + N(5) + 1

N(7) = 33 + 20 + 1                (Using (4) and (5))

∴ N(7) = 54                            …………(6)

 

So, minimum number of nodes required to construct AVL tree of height-7 = 54.

 

Step-07:

 

Substituting H = 8 in the recursive relation, we get-

N(8) = N(8-1) + N(8-2) + 1

N(8) = N(7) + N(6) + 1

N(8) = 54 + 33 + 1                (Using (5) and (6))

∴ N(8) = 88                            …………(6)

 

So, minimum number of nodes required to construct AVL tree of height-8 = 88.

 

But given number of nodes = 77 which is less than 88.

Thus, maximum height of AVL tree that can be obtained using 77 nodes = 7.

 

Next Article- Insertion in AVL Tree

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

AVL Tree Insertion | Insertion in AVL Tree

AVL Tree-

 

Before you go through this article, make sure that you have gone through the previous article on AVL Trees.

 

We have discussed-

  • AVL trees are self-balancing binary search trees.
  • In AVL trees, balancing factor of each node is either 0 or 1 or -1.

 

In this article, we will discuss insertion in AVL tree.

 

Insertion in AVL Tree-

 

Insertion Operation is performed to insert an element in the AVL Tree.

 

To insert an element in the AVL tree, follow the following steps-

  • Insert the element in the AVL tree in the same way the insertion is performed in BST.
  • After insertion, check the balance factor of each node of the resulting tree.

 

Read More- Insertion in Binary Search Tree

 

Now, following two cases are possible-

 

Case-01:

 

  • After the insertion, the balance factor of each node is either 0 or 1 or -1.
  • In this case, the tree is considered to be balanced.
  • Conclude the operation.
  • Insert the next element if any.

 

Case-02:

 

  • After the insertion, the balance factor of at least one node is not 0 or 1 or -1.
  • In this case, the tree is considered to be imbalanced.
  • Perform the suitable rotation to balance the tree.
  • After the tree is balanced, insert the next element if any.

 

Also Read- AVL Tree Properties

 

Rules To Remember-

 

Rule-01:

 

After inserting an element in the existing AVL tree,

  • Balance factor of only those nodes will be affected that lies on the path from the newly inserted node to the root node.

 

Rule-02:

 

To check whether the AVL tree is still balanced or not after the insertion,

  • There is no need to check the balance factor of every node.
  • Check the balance factor of only those nodes that lies on the path from the newly inserted node to the root node.

 

Rule-03:

 

After inserting an element in the AVL tree,

  • If tree becomes imbalanced, then there exists one particular node in the tree by balancing which the entire tree becomes balanced automatically.
  • To re balance the tree, balance that particular node.

 

To find that particular node,

  • Traverse the path from the newly inserted node to the root node.
  • Check the balance factor of each node that is encountered while traversing the path.
  • The first encountered imbalanced node will be the node that needs to be balanced.

 

To balance that node,

  • Count three nodes in the direction of leaf node.
  • Then, use the concept of AVL tree rotations to re balance the tree.

 

PRACTICE PROBLEM BASED ON AVL TREE INSERTION-

 

Problem-

 

Construct AVL Tree for the following sequence of numbers-

50 , 20 , 60 , 10 , 8 , 15 , 32 , 46 , 11 , 48

 

Solution-

 

Step-01: Insert 50

 

 

Step-02: Insert 20

 

  • As 20 < 50, so insert 20 in 50’s left sub tree.

 

 

Step-03: Insert 60

 

  • As 60 > 50, so insert 60 in 50’s right sub tree.

 

 

Step-04: Insert 10

 

  • As 10 < 50, so insert 10 in 50’s left sub tree.
  • As 10 < 20, so insert 10 in 20’s left sub tree.

 

 

Step-05: Insert 8

 

  • As 8 < 50, so insert 8 in 50’s left sub tree.
  • As 8 < 20, so insert 8 in 20’s left sub tree.
  • As 8 < 10, so insert 8 in 10’s left sub tree.

 

 

To balance the tree,

  • Find the first imbalanced node on the path from the newly inserted node (node 8) to the root node.
  • The first imbalanced node is node 20.
  • Now, count three nodes from node 20 in the direction of leaf node.
  • Then, use AVL tree rotation to balance the tree.

 

Following this, we have-

 

 

Step-06: Insert 15

 

  • As 15 < 50, so insert 15 in 50’s left sub tree.
  • As 15 > 10, so insert 15 in 10’s right sub tree.
  • As 15 < 20, so insert 15 in 20’s left sub tree.

 

 

To balance the tree,

  • Find the first imbalanced node on the path from the newly inserted node (node 15) to the root node.
  • The first imbalanced node is node 50.
  • Now, count three nodes from node 50 in the direction of leaf node.
  • Then, use AVL tree rotation to balance the tree.

 

Following this, we have-

 

 

Step-07: Insert 32

 

  • As 32 > 20, so insert 32 in 20’s right sub tree.
  • As 32 < 50, so insert 32 in 50’s left sub tree.

 

 

Step-08: Insert 46

 

  • As 46 > 20, so insert 46 in 20’s right sub tree.
  • As 46 < 50, so insert 46 in 50’s left sub tree.
  • As 46 > 32, so insert 46 in 32’s right sub tree.

 

 

Step-09: Insert 11

 

  • As 11 < 20, so insert 11 in 20’s left sub tree.
  • As 11 > 10, so insert 11 in 10’s right sub tree.
  • As 11 < 15, so insert 11 in 15’s left sub tree.

 

 

Step-10: Insert 48

 

  • As 48 > 20, so insert 48 in 20’s right sub tree.
  • As 48 < 50, so insert 48 in 50’s left sub tree.
  • As 48 > 32, so insert 48 in 32’s right sub tree.
  • As 48 > 46, so insert 48 in 46’s right sub tree.

 

 

To balance the tree,

  • Find the first imbalanced node on the path from the newly inserted node (node 48) to the root node.
  • The first imbalanced node is node 32.
  • Now, count three nodes from node 32 in the direction of leaf node.
  • Then, use AVL tree rotation to balance the tree.

 

Following this, we have-

 

 

This is the final balanced AVL tree after inserting all the given elements.

 

To gain better understanding of AVL Tree Insertion,

Watch this Video Lecture

 

Next Article- Introduction to Hashing

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Time Complexity of Binary Search Tree

Binary Search Tree-

 

Before you go through this article, make sure that you have gone through the previous article on BST Operations.

 

Commonly performed operations on binary search tree are-

 

 

  1. Search Operation
  2. Insertion Operation
  3. Deletion Operation

 

In this article, we will discuss time complexity of BST Operations.

 

Time Complexity-

 

  • Time complexity of all BST Operations = O(h).
  • Here, h = Height of binary search tree

 

Now, let us discuss the worst case and best case.

 

Worst Case-

 

In worst case,

  • The binary search tree is a skewed binary search tree.
  • Height of the binary search tree becomes n.
  • So, Time complexity of BST Operations = O(n).

 

In this case, binary search tree is as good as unordered list with no benefits.

 

 

Best Case-

 

In best case,

  • The binary search tree is a balanced binary search tree.
  • Height of the binary search tree becomes log(n).
  • So, Time complexity of BST Operations = O(logn).

 

 

To gain better understanding about Time Complexity of BST Operations,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Introduction to AVL Trees

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

AVL Tree | AVL Tree Example | AVL Tree Rotation

AVL Tree-

 

  • AVL trees are special kind of binary search trees.
  • In AVL trees, height of left subtree and right subtree of every node differs by at most one.
  • AVL trees are also called as self-balancing binary search trees.

 

Also Read- Binary Search Trees

 

Example-

 

Following tree is an example of AVL tree-

 

 

This tree is an AVL tree because-

  • It is a binary search tree.
  • The difference between height of left subtree and right subtree of every node is at most one.

 

Following tree is not an example of AVL Tree-

 

 

This tree is not an AVL tree because-

  • The difference between height of left subtree and right subtree of root node = 4 – 2 = 2.
  • This difference is greater than one.

 

Balance Factor-

 

In AVL tree,

  • Balance factor is defined for every node.
  • Balance factor of a node = Height of its left subtree – Height of its right subtree

 

In AVL tree,

Balance factor of every node is either 0 or 1 or -1.

 

AVL Tree Operations-

 

Like BST Operations, commonly performed operations on AVL tree are-

  1. Search Operation
  2. Insertion Operation
  3. Deletion Operation

 

Also Read- Insertion in AVL Tree

 

After performing any operation on AVL tree, the balance factor of each node is checked.

There are following two cases possible-

 

Case-01:

 

  • After the operation, the balance factor of each node is either 0 or 1 or -1.
  • In this case, the AVL tree is considered to be balanced.
  • The operation is concluded.

 

Case-02:

 

  • After the operation, the balance factor of at least one node is not 0 or 1 or -1.
  • In this case, the AVL tree is considered to be imbalanced.
  • Rotations are then performed to balance the tree.

 

AVL Tree Rotations-

 

Rotation is the process of moving the nodes to make tree balanced.

 

Kinds of Rotations-

 

There are 4 kinds of rotations possible in AVL Trees-

 

 

  1. Left Rotation (LL Rotation)
  2. Right Rotation (RR Rotation)
  3. Left-Right Rotation (LR Rotation)
  4. Right-Left Rotation (RL Rotation)

 

Cases Of Imbalance And Their Balancing Using Rotation Operations-

 

Case-01:

 

 

Case-02:

 

 

Case-03:

 

 

Case-04:

 

 

To gain better understanding about AVL Trees and Rotations,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- AVL Tree Properties

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Binary Search Tree Traversal | BST Traversal

Binary Search Tree-

 

Before you go through this article, make sure that you have gone through the previous article on Binary Search Trees.

 

Binary search tree (BST) is a special kind of binary tree where each node contains-

  • Only larger values in its right subtree.
  • Only smaller values in its left subtree.

 

In this article, we will discuss about Binary Search Tree Traversal.

 

BST Traversal-

 

  • A binary search tree is traversed in exactly the same way a binary tree is traversed.
  • In other words, BST traversal is same as binary tree traversal.

 

Read More- Binary Tree Traversal

 

Example-

 

Consider the following binary search tree-

 

 

Now, let us write the traversal sequences for this binary search tree-

 

Preorder Traversal-

 

100 , 20 , 10 , 30 , 200 , 150 , 300

 

Inorder Traversal-

 

10 , 20 , 30 , 100 , 150 , 200 , 300

 

Postorder Traversal-

 

10 , 30 , 20 , 150 , 300 , 200 , 100

 

Important Notes-

 

Note-01:

 

  • Inorder traversal of a binary search tree always yields all the nodes in increasing order.

 

Note-02:

 

Unlike Binary Trees,

  • A binary search tree can be constructed using only preorder or only postorder traversal result.
  • This is because inorder traversal can be obtained by sorting the given result in increasing order.

 

To gain better understanding about Binary Search Tree Traversal,

Watch this Video Lecture

 

PRACTICE PROBLEMS BASED ON BST TRAVERSAL-

 

Problem-01:

 

Suppose the numbers 7 , 5 , 1 , 8 , 3 , 6 , 0 , 9 , 4 , 2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers.

What is the inorder traversal sequence of the resultant tree?

  1. 7 , 5 , 1 , 0 , 3 , 2 , 4 , 6 , 8 , 9
  2. 0 , 2 , 4 , 3 , 1 , 6 , 5 , 9 , 8 , 7
  3. 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9
  4. 9 , 8 , 6 , 4 , 2 , 3 , 0 , 1 , 5 , 7

 

Solution-

 

This given problem may be solved in the following two ways-

 

Method-01:

 

  • We construct a binary search tree for the given elements.
  • We write the inorder traversal sequence from the binary search tree so obtained.

 

Following these steps, we have-

 

 

Thus, Option (C) is correct.

 

Method-02:

 

We know, inorder traversal of a binary search tree always yields all the nodes in increasing order.

 

Using this result,

  • We arrange all the given elements in increasing order.
  • Then, we report the sequence so obtained as inorder traversal sequence.

 

Inorder Traversal :

0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9

 

Thus, Option (C) is correct.

 

Problem-02:

 

The preorder traversal sequence of a binary search tree is-

30 , 20 , 10 , 15 , 25 , 23 , 39 , 35 , 42

What one of the following is the postorder traversal sequence of the same tree?

  1. 10 , 20 , 15 , 23 , 25 , 35 , 42 , 39 , 30
  2. 15 , 10 , 25 , 23 , 20 , 42 , 35 , 39 , 30
  3. 15 , 20 , 10 , 23 , 25 , 42 , 35 , 39 , 30
  4. 15 , 10 , 23 , 25 , 20 , 35 , 42 , 39 , 30

 

Solution-

 

In this question,

  • We are provided with the preorder traversal sequence.
  • We write the inorder traversal sequence by arranging all the numbers in ascending order.

 

Then-

  • Postorder Traversal : 30 , 20 , 10 , 15 , 25 , 23 , 39 , 35 , 42
  • Inorder Traversal : 10 , 15 , 20 , 23 , 25 , 30 , 35 , 39 , 42

 

Now,

  • We draw a binary search tree using these traversal results.
  • The binary search tree so obtained is as shown-

 

 

Now, we write the postorder traversal sequence-

 

Postorder Traversal :

15 , 10 , 23 , 25, 20, 35, 42, 39, 30

 

Thus, Option (D) is correct.

 

To watch video solutions and practice more problems,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Binary Search Tree Operations

 

Get more notes and other study material of Data Structures.

Watch video lectures by visiting our YouTube channel LearnVidFun.