Tree

o A Tree is a recursive data structure containing the set of one or more data nodes
where one node is designated as the root of the tree while the remaining nodes
are called as the children of the root.

Tree Terminology-
The important terms related to tree data structure are-

o Root Node :- The root node is the topmost node in the tree hierarchy. In other
words, the root node is the one which doesn't have any parent.
o Sub Tree :- If the root node is not null, the tree T1, T2 and T3 is called sub-trees
of the root node.
 o Leaf Node :- The node of tree, which doesn't have any child node, is called leaf
node. Leaf node is the bottom most node of the tree. There can be any number of
leaf nodes present in a general tree. Leaf nodes can also be called external
nodes.
o Path :- The sequence of consecutive edges is called path. In the tree shown in
the above image, path to the node E is A→ B → E.
o Ancestor node :- An ancestor of a node is any predecessor node on a path from
root to that node. The root node doesn't have any ancestors. In the tree shown in
the above image, the node F have the ancestors, B and A.
o Degree :- Degree of a node is equal to number of children, a node have. In the
tree shown in the above image, the degree of node B is 2. Degree of a leaf node
is always 0 while in a complete binary tree, degree of each node is equal to 2.
o Level Number :- Each node of the tree is assigned a level number in such a way
that each node is present at one level higher than its parent. Root node of the
tree is always present at level 0.

Static representation of tree

1. #define MAXNODE 500  
2. struct treenode {  
3.     int root;  
4.     int father;  
5.     int son;  
6.     int next;   
7. }

Why Trees?

1. One reason to use trees might be because you want to store information that
naturally forms a hierarchy. For example, the file system on a computer:

2. Trees (with some ordering e.g., BST) provide moderate access/search (quicker than
Linked List and slower than arrays).

3. Trees provide moderate insertion/deletion (quicker than Arrays and slower than
Unordered Linked Lists).

4. Like Linked Lists and unlike Arrays, Trees don’t have an upper limit on number of
nodes as nodes are linked using pointers.

Main applications of trees include:

1. Manipulate hierarchical data.

2. Make information easy to search (see tree traversal).

3. Manipulate sorted lists of data.

4. As a workflow for compositing digital images for visual effects.

5. Router algorithms

6. Form of a multi-stage decision-making (see business chess).   

Other Applications :
1. Heap is a tree data structure which is implemented using arrays and used
to implement priority queues.
2. B-Tree and B+ Tree : They are used to implement indexing in databases.
3. Syntax Tree: Used in Compilers.
4. K-D Tree: A space partitioning tree used to organize points in K
dimensional space.
5. Trie : Used to implement dictionaries with prefix lookup.
6. Suffix Tree : For quick pattern searching in a fixed text.

Types of Tree
The tree data structure can be classified into six different categories.

General Tree
General Tree stores the elements in a hierarchical order in which the top level element is
always present at level 0 as the root element.

Forests
Forest can be defined as the set of disjoint trees which can be obtained by deleting the
root node and the edges which connects root node to the first level node.
Tournament Tree
Tournament tree are used to record the winner of the match in each round being played
between two players. Tournament tree can also be called as selection tree or winner
tree. External nodes represent the players among which a match is being played while
the internal nodes represent the winner of the match played. At the top most level, the
winner of the tournament is present as the root node of the tree.

Binary Tree: A tree whose elements have at most 2 children is called a binary
tree. Since each element in a binary tree can have only 2 children, we typically
name them the left and right child.
Binary Tree Representation in C: A tree is represented by a pointer to the
topmost node in tree. If the tree is empty, then value of root is NULL.
A Tree node contains following parts.
1. Data
2. Pointer to left child
3. Pointer to right child

struct node

{
 int data;

struct node *left;

struct node *right;

};

Types of Binary Tree

Binary Tree-

Binary tree is a special tree data structure in which each node can have at most 2 children.

Thus, in a binary tree,

Each node has either 0 child or 1 child or 2 children.

Example-

Unlabeled Binary Tree-
 

A binary tree is unlabeled if its nodes are not assigned any label.

How many different Unlabeled Binary Trees can be there with n nodes?

T(n) = (2n)! / (n+1)!n!

Example-

Consider we want to draw all the binary trees possible with 3 unlabeled nodes.

Using the above formula, we have-

Number of binary trees possible with 3 unlabeled nodes

= 2 x 3C3 / (3 + 1)

= 6C3 / 4

= 5

Thus,

 With 3 unlabeled nodes, 5 unlabeled binary trees are possible.

 These unlabeled binary trees are as follows-
Labeled Binary Tree-

A binary tree is labeled if all its nodes are assigned a label.

Number of Labeled Tees = (Number of unlabeled trees) * n!

= [(2n)! / (n+1)!n!] × n!

Example-

Consider we want to draw all the binary trees possible with 3 labeled nodes.

Using the above formula, we have-

Number of binary trees possible with 3 labeled nodes

= { 2 x 3C3 / (3 + 1) } x 3!

= { 6C3 / 4 } x 6
= 5 x 6

= 30

Thus,

 With 3 labeled nodes, 30 labeled binary trees are possible.

 Each unlabeled structure gives rise to 3! = 6 different labeled structures.

Similarly,

 Every other unlabeled structure gives rise to 6 different labeled structures.

 Thus, in total 30 different labeled binary trees are possible.

Types of Binary Trees- 

Binary trees can be of the following types-

 
 1. Rooted Binary Tree
2. Full / Strictly Binary Tree
3. Complete / Perfect Binary Tree
4. Almost Complete Binary Tree
5. Skewed Binary Tree

1. Rooted Binary Tree-

A rooted binary tree is a binary tree that satisfies the following 2 properties-

 It has a root node.

 Each node has at most 2 children.

Example-

 Full / Strictly Binary Tree-

  

 A binary tree in which every node has either 0 or 2 children is called as a Full binary
tree.
 Full binary tree is also called as Strictly binary tree.
 
Example-
 

Complete / Perfect Binary Tree-

 
A complete binary tree is a binary tree that satisfies the following 2 properties-

 Every internal node has exactly 2 children.

 All the leaf nodes are at the same level.
 
Complete binary tree is also called as Perfect binary tree.
 
Example-
 
  

Almost Complete Binary Tree-

 
An almost complete binary tree is a binary tree that satisfies the following 2 properties-

 All the levels are completely filled except possibly the last level.
 The last level must be strictly filled from left to right.
 
Example-
 

5. Skewed Binary Tree- 

A skewed binary tree is a binary tree that satisfies the following 2 properties-

 All the nodes except one node has one and only one child.
 The remaining node has no child.
OR

A skewed binary tree is a binary tree of n nodes such that its depth is (n-1).

Example-

Continuous Tree
A tree is Continuous tree if in each root to leaf path, absolute difference between keys of two
adjacent is 1. We are given a binary tree, we need to check if tree is continuous or not.
Examples:
Input : 3
/ \
2 4
/ \ \
1 3 5
Output: "Yes"

// 3->2->1 every two adjacent node's absolute difference is 1

// 3->2->3 every two adjacent node's absolute difference is 1
// 3->4->5 every two adjacent node's absolute difference is 1

Input : 7
/ \
5 8
/ \ \
6 4 10
Output: "No"

// 7->5->6 here absolute difference of 7 and 5 is not 1.

// 7->5->4 here absolute difference of 7 and 5 is not 1.
// 7->8->10 here absolute difference of 8 and 10 is not 1.
Foldable Binary Trees
A tree can be folded if left and right subtrees of the tree are structure wise mirror image of
each other. An empty tree is considered as foldable.
Consider the below trees:
(a) and (b) can be folded.
(c) and (d) cannot be folded.

(a)
10
/ \
7 15
\ /
9 11

(b)
10
/ \
7 15
/ \
9 11

(c)
10
/ \
7 15
/ /
5 11

(d)

10
/ \
7 15
/ \ /
9 10 12
Expression Tree

Symmetric Tree (Mirror Image of itself)

For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3
But the following is not:
1
/ \
2 2
\ \
3 3

Balanced Binary Tree

A binary tree is balanced if the height of the tree is O(Log n) where n is the
number of nodes. For Example, AVL tree,Red-black trees

A degenerate (or pathological) tree A Tree where every internal node has one
child. Such trees are performance-wise same as linked list.
10
/
20
\
30
 \
40

Binary Tree Representations

A binary tree data structure is represented using two methods. Those methods are as

follows...

1. Array Representation

2. Linked List Representation

Consider the following binary tree...

1. Array Representation of Binary Tree

In array representation of a binary tree, we use one-dimensional array (1-D Array) to

represent a binary tree.

Consider the above example of a binary tree and it is represented as follows...

To represent a binary tree of depth 'n' using array representation, we need one dimensional

array with a maximum size of 2n + 1.

2. Linked List Representation of Binary Tree

We use a double linked list to represent a binary tree. In a double linked list, every node

consists of three fields. First field for storing left child address, second for storing actual data

and third for storing right child address.

In this linked list representation, a node has the following structure...

The above example of the binary tree represented using Linked list representation is shown

as follows...

Binary Tree Properties-

Important properties of binary trees are-

Property-01:
 
 Minimum number of nodes in a binary tree of height H

=H+1

Example-
To construct a binary tree of height = 4, we need at least 4 + 1 = 5 nodes.
 

Property-02:
 

Maximum number of nodes in a binary tree of height H

= 2H+1 – 1

 
Example-
 
Maximum number of nodes in a binary tree of height 3
= 23+1 – 1
= 16 – 1
= 15 nodes
Thus, in a binary tree of height = 3, maximum number of nodes that can be inserted =
15.
 
 
We can not insert more number of nodes in this binary tree.
 

Property-03:
 

Total Number of leaf nodes in a Binary Tree

= Total Number of Degree-2 nodes + 1

 
Example-
 
Consider the following binary tree-
 
  
Here,

 Number of leaf nodes = 3

 Number of degree-2 nodes = 2
 
Clearly, number of leaf nodes is one greater than number of degree-2 nodes.
This verifies the above relation.
 

NOTE
It is interesting to note that-
Number of leaf nodes in any binary tree depends only on the number of degree-2 nodes.

Property-04:
 

Maximum number of nodes at any level ‘L’ in a binary tree

= 2L

 
Example-
 
Maximum number of nodes at level-2 in a binary tree
= 22
=4
Thus, in a binary tree, maximum number of nodes that can be present at level-2 = 4.
 
  

5) In Binary tree where every node has 0 or 2 children, number of leaf

nodes is always one more than nodes with two children.
L = T + 1
Where L = Number of leaf nodes
T = Number of internal nodes with two children

PRACTICE PROBLEMS BASED ON BINARY TREE

PROPERTIES-

Problem-01:
A binary tree T has n leaf nodes. The number of nodes of degree-2 in T is ______?
1. log2n
2. n-1
3. n
4. 2n
Solution-
Using property-3, we have-
Number of degree-2 nodes
= Number of leaf nodes – 1
=n–1
 
Thus, Option (B) is correct.
 

Problem-02:
In a binary tree, for every node the difference between the number of nodes in the left
and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum
number of nodes in the tree is ______?
1. 2h-1
2. 2h-1 + 1
3. 2h – 1
4. 2h
Solution-
Let us assume any random value of h. Let h = 3.
Then the given options reduce to-
1. 4
2. 5
3. 7
4. 8
Now, consider the following binary tree with height h = 3-
 

 This binary tree satisfies the question constraints.

 It is constructed using minimum number of nodes.
Thus, Option (B) is correct.

Problem-03:
In a binary tree, the number of internal nodes of degree-1 is 5 and the number of internal
nodes of degree-2 is 10. The number of leaf nodes in the binary tree is ______?
1. 10
2. 11
3. 12
4. 15
Solution-
Using property-3, we have-
Number of leaf nodes in a binary tree
= Number of degree-2 nodes + 1
= 10 + 1
= 11
Thus, Option (B) is correct.

Problem-04:
The height of a binary tree is the maximum number of edges in any root to leaf path. The
maximum number of nodes in a binary tree of height h is ______?
1. 2h
2. 2h-1 – 1
3. 2h+1 – 1
4. 2h+1
 Solution-
Using property-2, Option (C) is correct.

Problem-05:
A binary tree T has 20 leaves. The number of nodes in T having 2 children is ______?

Solution-
Using property-3, correct answer is 19.

Binary Tree Traversal 

A Tree is typically traversed in two ways:
 Breadth First Traversal (Or Level Order Traversal)
 Depth First Traversals
 Inorder Traversal (Left-Root-Right)
 Preorder Traversal (Root-Left-Right)
 Postorder Traversal (Left-Right-Root)

BFS and DFSs of above Tree

Breadth First Traversal : 1 2 3 4 5

Depth First Traversals:

Preorder Traversal : 1 2 4 5 3
Inorder Traversal : 4 2 5 1 3
Postorder Traversal : 4 5 2 3 1

Inorder traversal
1. First, visit all the nodes in the left subtree
2. Then the root node
3. Visit all the nodes in the right subtree

1. inorder(root->left)
2. display(root->data)
3. inorder(root->right)
 Preorder traversal
1. Visit root node
2. Visit all the nodes in the left subtree
3. Visit all the nodes in the right subtree

1. display(root->data)
2. preorder(root->left)
3. preorder(root->right)

Postorder traversal
1. visit all the nodes in the left subtree
2. visit the root node
3. visit all the nodes in the right subtree

1. postorder(root->left)
2. postorder(root->right)
3. display(root->data)

1. Preorder Traversal-
 

Algorithm-
 
1. Visit the root
2. Traverse the left sub tree i.e. call Preorder (left sub tree)
3. Traverse the right sub tree i.e. call Preorder (right sub tree)
 

Root → Left → Right

Example-
Consider the following example-
 
  

Preorder Traversal Shortcut

 
Traverse the entire tree starting from the root node keeping yourself to the left.
 

Applications-
 

 Preorder traversal is used to get prefix expression of an expression tree.

 Preorder traversal is used to create a copy of the tree.
 

2. Inorder Traversal-
 
 Algorithm-
 
1. Traverse the left sub tree i.e. call Inorder (left sub tree)
2. Visit the root
3. Traverse the right sub tree i.e. call Inorder (right sub tree)
 

Left → Root → Right
 

Example-
 
Consider the following example-

Inorder Traversal Shortcut

 
Keep a plane mirror horizontally at the bottom of the tree and take the projection of all the nodes.
 Application-
 

 Inorder traversal is used to get infix expression of an expression tree.

 

3. Postorder Traversal-
 

Algorithm-
 
1. Traverse the left sub tree i.e. call Postorder (left sub tree)
2. Traverse the right sub tree i.e. call Postorder (right sub tree)
3. Visit the root
 

Left → Right → Root
 

Example-
 
Consider the following example-
 
 Postorder Traversal Shortcut
 

Pluck all the leftmost leaf nodes one by one.

Applications-
 

 Postorder traversal is used to get postfix expression of an expression tree.

 Postorder traversal is used to delete the tree.
 This is because it deletes the children first and then it deletes the parent.
 

Breadth First Traversal-

 
 Breadth First Traversal of a tree prints all the nodes of a tree level by level.
 Breadth First Traversal is also called as Level Order Traversal.
 

Example-
 

Application-
 

 Level order traversal is used to print the data in the same order as stored in the
array representation of a complete binary tree.
 
To gain better understanding about Tree Traversal,

PRACTICE PROBLEMS BASED ON TREE

TRAVERSAL-
 

Problem-01:
 
If the binary tree in figure is traversed in inorder, then the order in which the nodes will
be visited is ____?
 
 

Solution-
 
The inorder traversal will be performed as-
 

Problem-02:
 
Which of the following sequences denotes the postorder traversal sequence of the tree
shown in figure?
  

 
1. FEGCBDBA
2. GCBDAFE
3. GCDBFEA
4. FDEGCBA
 
Solution-
 
Perform the postorder traversal by plucking all the leftmost leaf nodes one by one.
Then,
Postorder Traversal :  G , C , D , B , F , E , A
 
Thus, Option (C) is correct.
 

Problem-03:
 
Let LASTPOST, LASTIN, LASTPRE denote the last vertex visited in a postorder, inorder
and preorder traversal respectively of a complete binary tree. Which of the following is
always true?
1. LASTIN = LASTPOST
2. LASTIN = LASTPRE
3. LASTPRE = LASTPOST
4. None of these
 

Solution-
 
Consider the following complete binary tree-
 

 
Preorder Traversal  : B , A , E
Inorder Traversal     : B , A , E
Postorder Traversal : B , E , A
 
Clearly, LASTIN = LASTPRE.
Thus, Option (B) is correct.
 

Problem-04:
 
Which of the following binary trees has its inorder and preorder traversals as BCAD and
ABCD respectively-
 
 

Solution-
 
Option (D) is correct.

PROGRAM (Recursive)
1. #include <stdio.h>
2. #include <stdlib.h>
3.
4. struct node {
5. int data;
6. struct node* left;
7. struct node* right;
8. };
9.
10. void inorder(struct node* root){
11. if(root == NULL) return;
12. inorder(root->left);
13. printf("%d ->", root->data);
14. inorder(root->right);
15. }
16.
17. void preorder(struct node* root){
18. if(root == NULL) return;
19. printf("%d ->", root->data);
20. preorder(root->left);
21. preorder(root->right);
22. }
23.
24. void postorder(struct node* root) {
25. if(root == NULL) return;
26. postorder(root->left);
27. postorder(root->right);
28. printf("%d ->", root->data);
29. }
30.
31.
32. struct node* createNode(value){
33. struct node* newNode = malloc(sizeof(struct node));
34. newNode->data = value;
35. newNode->left = NULL;
36. newNode->right = NULL;
37.
38. return newNode;
39. }
40.
41. struct node* insertLeft(struct node *root, int value) {
42. root->left = createNode(value);
43. return root->left;
44. }
45.
46.
47. struct node* insertRight(struct node *root, int value){
48. root->right = createNode(value);
49. return root->right;
50. }
51.
52.
53. int main(){
54. struct node* root = createNode(1);
55. insertLeft(root, 12);
56. insertRight(root, 9);
57.
58. insertLeft(root->left, 5);
59. insertRight(root->left, 6);
60.
61. printf("Inorder traversal \n");
62. inorder(root);
63.
64. printf("\nPreorder traversal \n");
65. preorder(root);
66.
67. printf("\nPostorder traversal \n");
68. postorder(root);
69. }

The output of the code will be

Inorder traversal
5 ->12 ->6 ->1 ->9 ->
Preorder traversal
1 ->12 ->5 ->6 ->9 ->
Postorder traversal
5 ->6 ->12 ->9 ->1 ->
 Binary Search Tree Construction
Binary Search Tree-
 

Binary Search Tree is a special kind of binary tree in which nodes are arranged in a specific
order.

 
In a binary search tree (BST), each node contains-

 Only smaller values in its left sub tree

 Only larger values in its right sub tree
 

Example-
 

Number of Binary Search Trees-

 

 
 Example-
 
Number of distinct binary search trees possible with 3 distinct keys
= 2×3C3 / 3+1
= 6C3 / 4
=5
 If three distinct keys are A, B and C, then 5 distinct binary search trees are-

Binary Search Tree Construction-

 
Let us understand the construction of a binary search tree using the following example-
 

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 a sequence,

 Always consider the first element as the root node.

 Consider the given elements and insert them 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.
 

 PRACTICEPROBLEMS BASED ON BINARY

SEARCH TREES-
 

Problem-01:
 
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
_____.
1. (4, 7)
2. (7, 4)
3. (8, 3)
4. (3, 8)
 

Solution-
 
Using the above discussed steps, we will construct the binary search tree.
The resultant binary search tree will be-
 

 
Clearly,

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

 Number of nodes in the right subtree of the root = 4
 
Thus, Option (B) is correct.
 

Problem-02:
  
How many distinct binary search trees can be constructed out of 4 distinct keys?
1. 5
2. 14
3. 24
4. 35
 

Solution-
 
Number of distinct binary search trees possible with 4 distinct keys
= 2nCn / n+1
= 2×4C4 / 4+1
= 8C4 / 5
= 14
 
Thus, Option (B) is correct.
 

Problem-03:
 
The numbers 1, 2, …, n are inserted in a binary search tree in some order. In the
resulting tree, the right subtree of the root contains p nodes. The first number to be
inserted in the tree must be-
1. p
2. p+1
3. n-p
4. n-p+1
 

Solution-
 
Let n = 4 and p = 3.
 
Then, given options reduce to-
1. 3
2. 4
3. 1
4. 2
Our binary search tree will be as shown-
  

Clearly, first inserted number = 1.

Thus, Option (C) is correct.

Problem-04:
 
We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In
how many ways can we populate the tree with given set so that it becomes a binary
search tree?
1. 0
2. 1
3. n!
4. C(2n, n) / n+1 
Solution-
 
Option (B) is correct.
 

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.
Binary Search Tree Operations-
  
Commonly performed operations on binary search tree are-
 

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

1. Search Operation-
 

Search Operation is performed to search a particular element in the Binary Search Tree.

Rules-
 
For searching a given key in the BST,

 Compare the key with the value of root node.

 If the key is present at the root node, then return the root node.
 If the key is greater than the root node value, then recur for the root node’s right
subtree.
 If the key is smaller than the root node value, then recur for the root node’s left
subtree.
 

Example-
 
Consider key = 45 has to be searched in the given BST-
 
  

 We start our search from the root node 25.

 As 45 > 25, so we search in 25’s right subtree.
 As 45 < 50, so we search in 50’s left subtree.
 As 45 > 35, so we search in 35’s right subtree.
 As 45 > 44, so we search in 44’s right subtree but 44 has no subtrees.
 So, we conclude that 45 is not present in the above BST.
 

2. Insertion Operation-
 

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

Rules-
 
The insertion of a new key always takes place as the child of some leaf node.
For finding out the suitable leaf node,

 Search the key to be inserted from the root node till some leaf node is reached.
 Once a leaf node is reached, insert the key as child of that leaf node.
Example-
Consider the following example where key = 40 is inserted in the given BST-
 We start searching for value 40 from the root node 100.
 As 40 < 100, so we search in 100’s left subtree.
 As 40 > 20, so we search in 20’s right subtree.
 As 40 > 30, so we add 40 to 30’s right subtree.
 

3. Deletion Operation-
 

Deletion Operation is performed to delete a particular element from the Binary Search Tree.

 
When it comes to deleting a node from the binary search tree, following three cases are
possible-
 
Case-01: Deletion Of A Node Having No Child (Leaf Node)-
 
Just remove / disconnect the leaf node that is to deleted from the tree.
 
Example-
 
Consider the following example where node with value = 20 is deleted from the BST-
 
  
Case-02: Deletion Of A Node Having Only One Child-
 
Just make the child of the deleting node, the child of its grandparent.
 
Example-
 
Consider the following example where node with value = 30 is deleted from the BST-
 

 
Case-02: Deletion Of A Node Having Two Children-
 
A node with two children may be deleted from the BST in the following two ways-
 
Method-01:
 

 Visit to the right subtree of the deleting node.

 Pluck the least value element called as inorder successor.
 Replace the deleting element with its inorder successor.
 
 Example-
 
Consider the following example where node with value = 15 is deleted from the BST-
 

Method-02:
 

 Visit to the left subtree of the deleting node.

 Pluck the greatest value element called as inorder predecessor.
 Replace the deleting element with its inorder predecessor.
 
Example-
 
Consider the following example where node with value = 15 is deleted from the BST-
 

Program to implement BST operations

#include <iostream>
#include <stdlib.h>
using namespace std;
struct Node {
int data;
 Node *left;
Node *right;
};
Node* create(int item)
{
Node* node = new Node;
node->data = item;
node->left = node->right = NULL;
return node;
}

void inorder(Node *root)

{
if (root == NULL)
return;

inorder(root->left);
cout<< root->data << " ";
inorder(root->right);
}
Node* findMinimum(Node* cur)
{
while(cur->left != NULL) {
cur = cur->left;
}
return cur;
}
Node* insertion(Node* root, int item)
{
if (root == NULL)
return create(item);
if (item < root->data)
root->left = insertion(root->left, item);
else
root->right = insertion(root->right, item);

return root;
}

void search(Node* &cur, int item, Node* &parent)

{
while (cur != NULL && cur->data != item)
{
parent = cur;
 if (item < cur->data)
cur = cur->left;
else
cur = cur->right;
}
}

void deletion(Node*& root, int item)

{
Node* parent = NULL;
Node* cur = root;

search(cur, item, parent);

if (cur == NULL)
return;

if (cur->left == NULL && cur->right == NULL)

{
if (cur != root)
{
if (parent->left == cur)
parent->left = NULL;
else
parent->right = NULL;
}
else
root = NULL;

free(cur);
}
else if (cur->left && cur->right)
{
Node* succ = findMinimum(cur- >right);
int val = succ->data;
deletion(root, succ->data);
cur->data = val;
}
else
{
Node* child = (cur->left)? Cur- >left: cur->right;

if (cur != root)
{
if (cur == parent->left)
parent->left = child;
 else
parent->right = child;
}

else
root = child;
free(cur);
}
}

int main()
{
Node* root = NULL;
int keys[8];
for(int i=0;i<8;i++)
{
cout << "Enter value to be inserted";
cin>>keys[i];
root = insertion(root, keys[i]);
}

inorder(root);
cout<<"\n";
deletion(root, 10);
inorder(root);
return 0;
}
Output:
Enter value to be inserted? 10
Enter value to be inserted? 20
Enter value to be inserted? 30
Enter value to be inserted? 40
Enter value to be inserted? 5
Enter value to be inserted? 25
Enter value to be inserted? 15
Enter value to be inserted? 5

5 5 10 15 20 25 30 40
5 5 15 20 25 30 40
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).
 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).
 

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.

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
 Balance Factor (k) = height (left(k)) - height (right(k))
 An AVL tree is given in the following figure. We can see that, balance factor
associated with each node is in between -1 and +1. therefore, it is an example of
AVL tree.
  

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

Complexity

Algorithm Average case Worst case

Space o(n) o(n)

Search o(log n) o(log n)

Insert o(log n) o(log n)

 Delete o(log n) o(log n)

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:
 

AVL Tree Properties

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.44log 2n.
 In other words, Worst case height of AVL Tree with n nodes = 1.44log 2n.
 

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.

B Tree
B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of
order m can have at most m-1 keys and m children. One of the main reason of using B
tree is its capability to store large number of keys in a single node and large key values
by keeping the height of the tree relatively small.

A B tree of order m contains all the properties of an M way tree. In addition, it contains
the following properties.
 1. Every node in a B-Tree contains at most m children.
2. Every node in a B-Tree except the root node and the leaf node contain at least
m/2 children.
3. The root nodes must have at least 2 nodes.
4. All leaf nodes must be at the same level.

It is not necessary that, all the nodes contain the same number of children but, each
node must have m/2 number of nodes.

A B tree of order 4 is shown in the following image.

While performing some operations on B Tree, any property of B Tree may violate such as
number of minimum children a node can have. To maintain the properties of B Tree, the
tree may split or join.

Operations
Searching :
Searching in B Trees is similar to that in Binary search tree. For example, if we search
for an item 49 in the following B Tree. The process will something like following :
 1. Compare item 49 with root node 78. since 49 < 78 hence, move to its left sub-
tree.
2. Since, 40<49<56, traverse right sub-tree of 40.
3. 49>45, move to right. Compare 49.
4. match found, return.

Searching in a B tree depends upon the height of the tree. The search algorithm takes
O(log n) time to search any element in a B tree.

Inserting
Insertions are done at the leaf node level. The following algorithm needs to be followed
in order to insert an item into B Tree.

1. Traverse the B Tree in order to find the appropriate leaf node at which the node
can be inserted.
2. If the leaf node contain less than m-1 keys then insert the element in the
increasing order.
3. Else, if the leaf node contains m-1 keys, then follow the following steps.
o Insert the new element in the increasing order of elements.
 o Split the node into the two nodes at the median.
o Push the median element upto its parent node.
o If the parent node also contain m-1 number of keys, then split it too by
following the same steps.

Example:

Insert the node 8 into the B Tree of order 5 shown in the following image.

8 will be inserted to the right of 5, therefore insert 8.

The node, now contain 5 keys which is greater than (5 -1 = 4 ) keys. Therefore split the
node from the median i.e. 8 and push it up to its parent node shown as follows.
Deletion
Deletion is also performed at the leaf nodes. The node which is to be deleted can either
be a leaf node or an internal node. Following algorithm needs to be followed in order to
delete a node from a B tree.

1. Locate the leaf node.

2. If there are more than m/2 keys in the leaf node then delete the desired key from
the node.
3. If the leaf node doesn't contain m/2 keys then complete the keys by taking the
element from eight or left sibling.
o If the left sibling contains more than m/2 elements then push its largest
element up to its parent and move the intervening element down to the
node where the key is deleted.
o If the right sibling contains more than m/2 elements then push its smallest
element up to the parent and move intervening element down to the node
where the key is deleted.
4. If neither of the sibling contain more than m/2 elements then create a new leaf
node by joining two leaf nodes and the intervening element of the parent node.
5. If parent is left with less than m/2 nodes then, apply the above process on the
parent too.

If the the node which is to be deleted is an internal node, then replace the node with its
in-order successor or predecessor. Since, successor or predecessor will always be on the
leaf node hence, the process will be similar as the node is being deleted from the leaf
node.

Example 1

Delete the node 53 from the B Tree of order 5 shown in the following figure.
53 is present in the right child of element 49. Delete it.

Now, 57 is the only element which is left in the node, the minimum number of elements
that must be present in a B tree of order 5, is 2. it is less than that, the elements in its
left and right sub-tree are also not sufficient therefore, merge it with the left sibling and
intervening element of parent i.e. 49.

The final B tree is shown as follows.

Application of B tree
B tree is used to index the data and provides fast access to the actual data stored on the
disks since, the access to value stored in a large database that is stored on a disk is a
very time consuming process.

Searching an un-indexed and unsorted database containing n key values needs O(n)
running time in worst case. However, if we use B Tree to index this database, it will be
searched in O(log n) time in worst case.