It is a type of data structure where the data elements are not arranged linearly or sequentially. These are multi-level data structures. Here, data components are exist at several levels. Elements of non-linear data structures are stores and accessed in non-linear order. In non-linear data structures, the elements are stored randomly.

In a non-linear data structure, data elements aren’t structured sequentially. Because the elements are not stored sequentially, they cannot be traversed or retrieved in a single run. Non-linear data structure is not very easy to implement as compared to the linear data structure

Examples of non-linear data structure are: Tree and Graph

TREE:

The tree is a non-linear data structure that is made up of various nodes. The nodes in the tree data system are set up in hierarchical order. A tree data structure is made up of nodes that are linked together. It is a nonlinear hierarchical data structure that consists of nodes connected by edges.

A tree has the following properties:

1. The tree has one node called root. The tree originates from this, and hence it does not have any parent.

2. Each node has one parent only but can have multiple children.

3. Each node is connected to its children via edges.

Representation of Tree:

In computer science the conventional way of representing a tree is upside down i.e., the root of the tree is at the top and the branches are in the downward direction.

Figure: A General Tree

Here the root of the tree is A. There are three subtrees of the root A, with roots B,D and G. The root B has one subtree. The root C has empty subtree. The root D and G have two and three subtrees respectively. The nodes (except root) having no subtrees are called leafs or terminal nodes.

In the above tree, C,E,F,H,I,J are the leaf nodes or terminal nodes. Any node (except the root and leafs) is called non-terminal node. Here, B,D and G are the non-terminal nodes. The node having at least a child node is called an internal node. G is an internal node.

Level of a Node:

The level of a node is equal to the length of the path from the root to the node. The root of the tree has level=0.

For example, in above tree the levels are:

Level of A=0

Level of B,D,G=1

Level of C,E,F,H,I,J=2

Degree of a node:

The degree of a node is the number of children it has. The degree of a leaf is 0. For example in above tree the degree of node D is 2.

Degree of a tree:

The degree of a tree is the maximum of its node degrees. The degree of tree in above figure is 3.

Height/Depth of a tree:

If level of the root is denoted by 0, then Height/Depth of tree =1+ maximum levels of all nodes in the tree. The height/depth of tree given in above figure is 3.

Parent and child relationship:

In above tree, the node A is parent of B, D and G. B, D and G are children of A. The children nodes of a given parent node are called siblings or brothers.

Ancestor of a Node:

Any predecessor nodes on the path of the root to that node are called Ancestors of that node. For example, in the above tree A and D are the ancestor of E.

Descendant:

Any successor node on the path from the leaf node to that node. B,C are the descendants of the node A.

More Tree Terminology:

The depth of a node is the number of edges from the root to the node.
The height of a node is the number of edges from the node to the deepest leaf.
The height of a tree is a height of the root.
A full binary tree is a binary tree in which each node has exactly zero or two children.
A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.

Advantages of Trees:

Trees are so useful and frequently used, because they have some very serious advantages:

Trees reflect structural relationships in the data
Trees are used to represent hierarchies
Trees provide an efficient insertion and searching
Trees are very flexible data, allowing to move subtrees around with minimum effort

Binary Tree:

A binary tree is a hierarchal data structure in which each node has at most two children. The Binary tree means that the node can have maximum two children. Here, binary name itself suggests that ‘two’; therefore, each node can have either 0, 1 or 2 children.

A binary tree is simply a tree in which each node can have at most two children. A binary tree is made of nodes, where each node contains a “left” reference, a “right” reference, and a data element. The topmost node in the tree is called the root.

A tree is called a binary tree if it has a finite set of nodes that is either empty or consists of a root and two disjoint subsets, each of which itself is a binary tree. The two subsets are called the left subtree and the right subtree of the original tree.

Binary trees are different from general trees. A binary tree has left and right subtrees, whereas, in general trees there is no left or right subtree.

Fig: Binary Tree

The above tree is a binary tree because each node contains the at most two children. Here, A is the root of the tree and it has two subtrees. The left subtree has root B and it also has two subtrees are D and E. The right subtree has root C and it has one subtree F. Subtrees D,E and F has no subtrees.

Properties of Binary Tree:

1. Every binary tree with n elements (n>0), has exactly n-1 edges.

2. A binary tree of height h (h>=0), has at least h and at most 2^h-1 elements in it.

3. A binary tree can have a maximum of 2^l nodes at level l if the level of the root is zero.

4. The height of a binary tree that contains n elements (n>=0), is at most n, at least log₂(n+1)

5. In a binary tree with n nodes, minimum possible height or minimum numbers of levels are log₂(n+1).

6. A binary tree with ‘L’ leaves has at least log₂(L+1) number of levels.

7. If a binary tree has 0 or 2 children, then number of leaf nodes are always one more than nodes with two children.

Types of Binary Tree:

There are various types of binary trees, and each of these binary tree types has unique characteristics.

1. Full Binary Tree:

The full binary tree is also known as a strict binary tree. A binary tree is said to be a full binary tree when each node has zero or two children. We can say it is a binary tree in which all nodes except leaf nodes have two children.

2. Complete Binary Tree:

A binary tree is referred to as a complete binary tree when all of its levels are completely filled except the lowest level of the tree. Also, in the last or the lowest level of this binary tree, every nodes should possibly reside on the left side.

3. Perfect Binary Tree:

A perfect binary tree is a special type of binary tree in which all the internal nodes have two children and every external or leaf node is at the same level.

4. Balanced Binary Tree:

A balanced binary tree also referred to as a height-balanced binary tree is also a special type of binary tree in which the difference of height between the left and the right subtrees for each node is at most one.

The above tree is a balanced binary tree because the difference between the left subtree and right subtree is not greater than 1.

5. Degenerate or Pathological Tree:

A degenerate or pathological tree is a type of binary tree in which each internal node has a single child, either the left child or the right child.

6. Skewed Binary Tree:

A binary tree is said to be a skewed binary tree if all of its internal nodes have exactly one child, and either left children or right children dominate the tree.

There exist two types of skewed binary trees: left-skewed binary tree and the right-skewed binary tree.

Fig: Left-skewed binary tree

Fig: Right-skewed binary tree

Problem-1:

How many binary tree can be created with 3 nodes?

a. 5

b. 6

c. 7

d. None of the above

Solution:

A binary tree with 3 nodes ( n=3) , will have a maximum combination of 5 different trees.

Problem-2: Total number of nodes in the n^th level of a binary tree is given by

a. 2ⁿ

b. 2^n-1

c. 2ⁿ⁺¹

d. 2n

Problem-3: Maximum total number of nodes in a binary tree that has n levels

a. 2ⁿ

b. 2^n-1

c. 2ⁿ⁺¹

d. 2n

Binary Search Tree:

Binary Search Tree is a special kind of binary tree in which nodes are arranged in a specific order. In binary search tree, the value of left node must be smaller than the parent node, and the value of right node must be greater than the parent node. This rule is applied recursively to the left and right subtrees of the root.

A binary search tree relies on the property that keys that are less than the parent are found in the left subtree, and keys that are greater than the parent are found in the right subtree.

A binary search tree is a binary tree that may be empty. A non-empty binary search tree satisfies the following properties:

Every element has a key (or value) and no two elements have the same key; therefore all keys are distinct.
The keys (if any) in the left subtree are smaller than the key in the root.
The keys (if any) in the right subtree are larger than the key in the root.
The left and right subtrees of the root are also binary search trees.

Example of a Binary Search Tree:

In the above figure, we can observe that the value of root node is 40, and the values of all nodes of the left subtree are smaller than the root node value, and the values of all nodes of the right subtree are greater than the root node value.

Binary Search Tree Construction: (Creating Binary Search Tree)

Constructing a Binary Search Tree (BST) involves inserting elements one by one into an initially empty tree or starting with a root node. The key property of a BST ensures that the left subtree of a node contains only nodes with keys less than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key.

Example:

Construct a Binary Search Tree (BST) for the following sequence of numbers-

50, 70, 60, 20, 90, 10, 40, 100

When elements are given in the sequence,

Always consider the first element as the root node
Consider the given elements and insert in the BST one by one

The binary search tree will be constructed as explained below:

Insert 50:

Insert 70:

As 70 > 50, so insert 70 to the right of 50.

Insert 60:

· As 60 > 50, so insert 60 to the right of 50.

· As 60 < 70, so insert 60 to the left of 70.

Insert 20:

As 20 < 50, so insert 20 to the left of 50.

Insert 90:

· As 90 > 50, so insert 90 to the right of 50.

· As 90 > 70, so insert 90 to the right of 70.

Insert 10:

· As 10 < 50, so insert 10 to the left of 50.

· As 10 < 20, so insert 10 to the left of 20.

Insert 40:

· As 40 < 50, so insert 40 to the left of 50.

· As 40 > 20, so insert 40 to the right of 20.

Insert 100:

· As 100 > 50, so insert 100 to the right of 50.

· As 100 > 70, so insert 100 to the right of 70.

· As 100 > 90, so insert 100 to the right of 90.

Now, the creation of binary search tree is completed.

PRACTICE PROBLEMS

Problem-1:

Construct a binary search tree for the following sequence of numbers:

7, 4, 12, 3, 6, 8, 1, 5, 10

Solution:

Insert 7:

Insert 4:

As 4<7, so insert 4 to the left of 7

Insert 12:

As 12>7, insert 12 to the right of 7

Insert 3:

· As 3<7, so insert 3 to the left of 7

· As 3<4, so insert 3 to the left of 4

Insert 6:

· As 6<7, so insert 6 to the left of 7

· As 6>4, insert 6 to the right of 4

Insert 8:

· As 8>7, insert 8 to the right of 7

· As 8<12, insert 8 to the left of 12

Insert 1:

· As 1<7, so insert 1 to the left of 7

· As 1<4, so insert 1 to the left of 4

· As 1<3, so insert 1 to the left of 3

Insert 5:

· As 5<7, so insert 5 to the left of 7

· As 5>4, insert 5 to the right of 4

· As 5<6, so insert 5 to the left of 6

Insert 10:

· As 10>7, insert 10 to the right of 7

· As 10<12, insert 10 to left of 12

· As 10>8, insert 10 to the right of 8

Now, the construction of binary search tree is completed.

Problem-2:

Create Binary Search Tree for the following sequence of numbers:

45, 15, 79, 90, 10, 55, 12, 20, 50

Solution:

Insert 45:

Insert 15

· As 15 <45, so insert 15 to the left of 45

Insert 79

· As 79 >45, so insert 79 to the right of 45

Insert 90

· As 90 >45, so insert 90 to the right of 45

· As 90 > 79, so insert 90 to the right of 79

Insert 10

· As 10 < 45, so insert 10 to the left of 45

· As 10 < 15, so insert 10 to the left of 15

Insert 55

· As 55 >45, so insert 55 to the right of 45

· As 55 <79, so insert 55 to the left of 79

Insert 12

· As 12 < 45, so insert 12 to the left of 45

· As 12 < 15, so insert 12 to the left of 15

· As 12 > 10, so insert 12 to the right of 10

Insert 20

· As 20 < 45, so insert 20 to the left of 45

· As 20 >15, so insert 20 to the right of 15

Insert 50

· As 50> 45, so insert 20 to the left of 45

· As 20 >15, so insert 20 to the right of 15

Now, the creation of binary search tree is completed.

Problem-3:

A Binary search tree is constructed by inserting the following number in order:

60, 25, 72, 15, 30, 68, 101, 13, 18, 47, 70, 34

The number of nodes in the left subtree is:

a. 7

b. 6

c. 3

d. 5

Insert 60

Insert 25:

As 25<60, so insert 25 to the left of 60

Insert 72

As 72> 60, so insert 72 to the right of 60

Insert 15:

· As 15<60, so insert 15 to the left of 60

· As 15 <25, so insert 15 to the left of 25

Insert 30

As 30<60, so insert 30 to the left of 60· As 30 >25, so insert 30 to the right of 25

Insert 68:

· As 68>60, so insert 68 to the right of 60

· As 68 <72, so insert 68 to the left of 72

Insert 101:

· As 101>60, so insert 101 to the right of 60

· As 101>72, so insert 101 to the right of 72

Insert 13:

· As 13<60, so insert 13 to the left of 60

· As 13<25, so insert 13 to the left of 25

· As 13<15, so insert 13 to the left of 15

Insert 18:

· As 18<60, so insert 18 to the left of 60

· As 18<25, so insert 18 to the left of 25

· As 18>15, so insert 18 to the right of 15

Insert 47:

· As 47<60, so insert 47 to the left of 60

· As 47>25, so insert 47 to the right of 25

· As 47>30, so insert 47 to the right of 30

Insert 70:

· As 70>60, so insert 70 to the right of 60

· As 70<72, so insert 70 to the left of 72

· As 70>68, so insert 70 to the right of 68

Insert 34:

· As 34<60, so insert 34 to the left of 60

· As 34>25, so insert 34 to the right of 25

· As 34>30, so insert 34 to the right of 30

· As 34<47, so insert 34 to the left of 47

Number of nodes in the left subtree of the root = 7

Problem-4:

A binary search tree is generated by inserting in order of the following integers-

50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24

The number of nodes in the left subtree and right subtree of the root respectively is _________________.

a. (4, 7)

b. (7, 4)

c. (8,3)

d. (3,8)

Solution:

The Binary Search Tree will be:

· Number of nodes in the left subtree of the root = 7

· Number of nodes in the right subtree of the root = 4

Problem-5:

How many distinct binary search trees can be constructed out of 4 distinct keys?

a. 5

b. 14

c. 24

d. 35

Solution:

Number of distinct binary search trees possible with 4 distinct keys

= ²ⁿC_n / n+1

= ^2×4C₄ / 4+1

= ⁸C₄ / 5

= 14

Thus, Option (B) is correct.

Insertion in Binary Search Tree:

Inserting a new node into a Binary Search Tree (BST) involves finding the correct position for the new node based on its key and then adding it as a leaf node. The key property of a BST ensures that the left subtree of a node contains only nodes with keys less than the node’s key, and the right subtree contains only nodes with keys greater than the node’s key.

We perform an insertion operation to insert any value in the binary search tree. If the tree is empty, the new element is inserted as the root node of the tree. Otherwise, the key of the new element is compared to the key of the root node to determine whether it must be inserted in the root’s left subtree or its right subtree.

Deletion in Binary Search Tree:

We must delete a node from a binary search tree in such a way, that the property of binary search tree doesn’t violate. A node’s right subtree only contains nodes with keys higher than the node’s key, and its left subtree only contains nodes with keys lower than the node’s key. A binary search tree must also be present in both the left and right subtrees.

In a Binary Search Tree (BST), deletion of a node involves three cases:

Case 1: Node with no children (Leaf Node):

In the first case, the node to be deleted is a leaf node (node with no children). In such a case, simply delete the node from the tree.

Case 2: Node with one child:

In the second case, the node to be deleted has only one child. In such a case, remove the node and replace it with its child.

Case 3: Node with two children:

In the third case, the node to be deleted has two children. Compare to the previous two cases, it is a little more complicated. However, the node which is to be deleted, is replaced with its in-order successor or predecessor.

Problem-1:

Consider the following binary search tree T:

Draw the resulting binary search tree if the following operation is performed to the tree T;

(i) Insert element 11 in T

(ii) Insert element 16 in T

(iii) Insert element 12 in T

(iv) Delete element 14 from T

Solution:

(i) Insert 11

(ii) Insert 16

(iii) Insert 12

(iv) Delete 14

Tree Traversal Methods:

A traversal is a process that visits all the nodes in the tree. The term ‘tree traversal’ means traversing or visiting each node in the tree exactly once and performing some operations on it. There are three ways which we use to traverse a tree –

Pre-order Traversal
In-order Traversal
Post-order Traversal

Pre-order Traversal:

In this traversal method, the root node is visited first, then the left subtree and finally the right subtree. As the root node is traversed before (or pre) the left and right subtree, it is called pre-order traversal. To traverse a non-empty binary tree in pre-order we perform the following three operations:

1. Visit the root.

2. Traverse the left subtree

3. Traverse the right subtree

In-order Traversal:

In this traversal method, the left subtree is visited first, then the root and later the right sub-tree. As the root node is traversed between the left and right subtree, it is named in-order traversal.

If a binary tree is traversed in-order, the output will produce sorted key values in an ascending order. To traverse a non-empty binary tree in in-order we perform the following three operations:

1. Traverse the left subtree.

2. Visit the root.

3. Traverse the right subtree.

Post-order Traversal:

In this traversal method the left subtree is visited first, then the right subtree and finally the root node. As the root node is traversed after (or post) the left and right subtree, it is called post order traversal. To traverse a non-empty binary tree in post-order we perform the following three operations:

1. Traverse the left subtree.

2. Traverse the right subtree.

3. Visit the root.

Example: 1

Pre-order: 3, 9, 20, 15, 7

In-order: 9, 3, 15, 20, 7

Post-order: 9, 15, 7, 20, 3

Example: 2

Pre-order: A, B, D, E, C, F, G

In-order: D, B, E, A, F, C, G

Post-order: D, E, B, F, G, C, A

Example: 3

Pre-order: 100, 20, 10, 30, 200, 150, 300

In-order: 10, 20, 30, 100, 150, 200, 300

Post-order: 10, 30, 20, 150, 300, 20, 100

Example: 4

Pre-order: – + A * B C * D E

In-order: A + B * C – D * E

Post-order: AB C * + D E * –

Example: 5

Pre-order: FBADCEGIH

In-order: ABCDEFGHI

Post-order: ACEDBHIGF

Example: 6

Pre-order: 8, 5, 9, 7, 1, 12, 2, 4, 11, 3
In-order: 9, 5, 1, 7, 2, 12, 8, 4, 3, 11
Post-order: 9, 1, 2, 12, 7, 5, 3, 11, 4, 8

Example: 7

Pre-order: 25, 15, 10, 4, 12, 22, 18, 24, 50, 35, 31, 44, 70, 66, 90

In-order: 4, 10, 12, 15, 18, 22, 24, 25, 31, 35, 44, 50, 66, 70, 90

Post-order: 4, 12, 10, 18, 24, 22, 15, 31, 44, 35, 66, 90, 70, 50, 25

Construct a Tree from given In-order and Pre-order Traversals:

In-order traversal is a special traversal that helps us to identify a node and its left and right subtree. Pre-order traversal always gives us the root node as the first element. Using these properties we can construct the unique binary tree.

Example-1:

In-order sequence: D B E A F C

Pre-order sequence: A B D E C F

In a Pre-order sequence, the leftmost element is the root of the tree. So we know ‘A’ is the root for given sequences. By searching ‘A’ in the In-order sequence, we can find out all elements on the left side of ‘A’ is in the left subtree and elements on right side of ‘A’ in the right subtree. So we get the below structure now.

Step: 1

We recursively follow the above steps and get the following tree.

Step: 2

Example-2:

In-order: 40, 20, 50, 10, 60, 30

Pre-order: 10, 20, 40, 50, 30, 60

Step-1:

Here 10 (first element of pre-order) is the root element. So we can find its index in the in-order traversal. The left subtree of the root will be present to the left side of in order whereas the right subtree of root will be present on the right side of root element in the in-order traversal.

Step: 2

Example-3:

In-order Traversal: 4, 2, 1, 7, 5, 8, 3, 6

Pre-order Traversal: 1, 2, 4, 3, 5, 7, 8, 6

Root node would be the first item in the pre-order sequence, and find the left and right subtree in the in-order sequence. To find left and right subtree, search for the index of the root node in the in-order sequence. All keys before the root node in the in-order sequence become part of the left subtree, and all keys after the root node become part of the right subtree. We repeat this recursively for all nodes in the tree and construct the tree.

Step: 1

The root will be the first element in the pre-order sequence, i.e., 1. Next, search the index of the root node in the in-order sequence. Since 1 is the root node, all nodes before 1 in the in-order sequence must be included in the left subtree, i.e., 4, 2 and all the nodes after 1 must be included in the right subtree, i.e., 7, 5, 8, 3, 6.

Now, we recursively follow the above steps and get the binary tree:

Step: 2

Step: 3

Problem-1: For a binary tree T, the pre-order and in-order traversal sequences are as follows:

Pre-order: A B D E G H C F

In-order: D B G E H A C F.

Draw the binary tree T.

Solution:

Step-1:

The root will be the first element in the pre-order sequence, i.e., `A`. Next, search the index of the root node in the in-order sequence. Since `A` is the root node, all nodes before `A` in the in-order sequence must be included in the left subtree, i.e., `D, B,G, E , H` and all the nodes after `A` must be included in the right subtree, i.e., `C, F.`

Step-2:

Now, we recursively follow the above steps and get the binary tree:

Step-3:

Problem-2:

For a binary tree T, the pre-order and in-order traversal sequences are as follows:

Pre-order: G B Q A C K F P D E R H

In-order: Q B K C F A G P E D H R

(a) What is the height of the tree?

(b) What are the internal nodes?

Solution:

Step-1:

The root will be the first element in the pre-order sequence, i.e., G. Next, search the index of the root node in the in-order sequence. Since G is the root node, all nodes before G in the in-order sequence must be included in the left subtree, i.e., Q, B,K, C , F, A and all the nodes after G must be included in the right subtree, i.e., P, E, D, H, R.

Step-2:

Now, we recursively follow the above steps and get the binary tree:

Step-3:

Step-4:

(a) The height of the tree is : 5

(b)The internal nodes are: B, A, C, P, D, R

(c) Post-order: QKFCABEHRDPG

Construct Binary Tree from given In-order and Post order Traversals:

Example-1:

In-order: 40 20 50 10 30 60

Post-order: 40 50 20 60 30 10

Step-1:

We first find the last node in post-order traversal. The last node is 10 , we know this value is root as root always appear in the end of post-order traversal.

We search 10 in in-order traversal to find left and right subtrees of root. Everything on left of 10 in in-order traversal is in left subtree and everything on right is in right subtree.

Step-2:

Example-2:

In-order: 10 30 40 50 60 70 90

Post-order: 10 40 30 60 90 70 50

Step-1:

We first find the last node in post-order traversal. The last node is 50 , we know this value is root as root always appear in the end of post-order traversal.

We search 50 in in-order traversal to find left and right subtrees of root. Everything on left of 50 in in-order traversal is in left subtree and everything on right is in right subtree.

Step-2:

Problem-3:

The in order and post order traversal of a binary tree are as follows:

In order: n1, n2, n3, n4, n5, n6, n7, n8, n9

Post-order: n1, n3, n5, n4, n2, n8, n7, n9, n6

Construct the binary tree.

Solution:

Step-1:

Step-2:

Step-3:

Problem-4:

For a binary tree T, the in-order and post-order traversal sequences are as follows:

In-order: D B F E A G C L J H K

Post-order: D F E B G L J K H C A

Draw the binary tree T.

Solution:

Step-1:

We first find the last node in post-order traversal. The last node is A, we know this value is root as root always appear in the end of post-order traversal.

We search A in in-order traversal to find left and right subtrees of root. Everything on left of A in in-order traversal is in left subtree and everything on right of A is in right subtree.

Step-2:

Step-3:

Step-4:

AVL TREE:

An AVL( Adelson-Velskii and Landis) tree is a type of binary search tree. AVL trees are Self Balanced binary search trees named after its inventors, Adelson-Velskii and Landis.

It is a balanced binary search tree. In AVL tree, the balance factor of every node is either -1 or 0 or 1. The balance factor of a node is the difference between the heights of the left and right subtrees of that node.

AVL tree is a height-balanced binary search tree. That means, an AVL tree is also a binary search tree but it is a balanced tree. AVL trees use balance factor to get a balanced tree. Balance factor of any node is defined as height(left subtree) – height(right subtree).

· AVL Trees are Self-Balanced Binary Search Trees.

· In AVL trees, the balancing factor of each node is either 0 or 1 or -1.

· Balance Factor of AVL Tree calculated as = Height of Left Sub-tree – Height of Right Sub-tree

Question: What is AVL tree? Construct an AVL tree with the following elements and perform necessary rotation if unbalance occurs while inserting the element.

8, 6, 10, 4, 7, 9, 11, 3, 5, 2

Ans: An AVL tree is a type of binary search tree. It is a balanced binary search tree. In AVL tree, the balance factor of every node is either -1 or 0 or 1. The balance factor of a node is the difference between the heights of the left and right subtrees of that node.

AVL tree is a height-balanced binary search tree. That means, an AVL tree is also a binary search tree but it is a balanced tree. AVL trees are Self Balanced binary search trees named after its inventors, Adelson-Velskii and Landis.

· AVL Trees are Self-Balanced Binary Search Trees.

· In AVL trees, the balancing factor of each node is either 0 or 1 or -1.

· Balance Factor of AVL Tree calculated as = Height of Left Sub-tree – Height of Right Sub-tree

Construction of AVL Tree:

· Insertion Operation is performed to construct the AVL Tree.

· Inserting the element in the AVL tree is same as the insertion performed in BST.

· After insertion, check the balance factor of each node of the resulting tree.

o After the insertion, the balance factor of each node is either 0 or 1 or -1, then the tree is considered to be balanced, concludes the operation, and inserts the next element if any.

o After the insertion, if the balance factor of at least one node is not 0 or 1 or -1, then the tree is considered to be imbalanced, perform the suitable rotation to balance the tree, and after the tree is balanced, insert the next element if any.

Step-1:

Insert 8