TREES

 Tree is a non-linear data structure which organizes data in hierarchical structure

 The top element(node) of the hierarchy is a root node.
 Each node can have at most one link coming into it. The node where the link originates is called
the parent node.
 The root node has no parent. Except the root, each element has a parent
 The links leaving a node (any number of links are allowed) point to child nodes.
 Trees are recursive structures. Each child node is itself the root of a subtree.
 At the bottom of the tree are leaf nodes, which have no children.
 each element has 0 or more children
 In tree data structure, every individual element is called as Node. Node in a tree data structure,
stores the actual data of that particular element and link to next element in hierarchical structure.
 In a tree data structure, if we have N number of nodes then we can have a maximum of N-1
number of links.

Example:

1. The organization structure of a corporation.(university,departments,faculty,students)

2. table of contents of a book.(book contains units, units contains chapters, chapters contains
several topics)
3. file structure

Tree Terminology:

1. Root

In a tree data structure, the first node is called as Root Node. Every tree must have root node.

We can say that root node is the origin of tree data structure. In any tree, there must be only one root node.
We never have multiple root nodes in a tree.
2. Edge

In a tree data structure, the connecting link between any two nodes is called as EDGE. In a tree with 'N'
number of nodes there will be a maximum of 'N-1' number of edges.

3. Parent

In a tree data structure, the node which is predecessor of any node is called as PARENT NODE.

In simple words, the node which has branch from it to any other node is called as parent node. Parent node
can also be defined as "The node which has child / children".

4. Child

In a tree data structure, the node which is descendant of any node is called as CHILD Node.

In simple words, the node which has a link from its parent node is called as child node. In a tree, any parent
node can have any number of child nodes. In a tree, all the nodes except root are child nodes.

5. Siblings

In a tree data structure, nodes which belong to same Parent are called as SIBLINGS. In simple words, the
nodes with same parent are called as Sibling nodes.
6. Leaf

In a tree data structure, the node which does not have a child is called as LEAF Node. In simple words, a
leaf is a node with no child.

In a tree data structure, the leaf nodes are also called as External Nodes. External node is also a node with no
child. In a tree, leaf node is also called as 'Terminal' node.

7. Internal Nodes

In a tree data structure, the node which has atleast one child is called as INTERNAL Node. In simple
words, an internal node is a node with atleast one child.

In a tree data structure, nodes other than leaf nodes are called as Internal Nodes. The root node is also said
to be Internal Node if the tree has more than one node. Internal nodes are also called as 'Non-Terminal'
nodes.

8. Degree

In a tree data structure, the total number of children of a node is called as DEGREE of that Node. In
simple words, the Degree of a node is total number of children it has. The highest degree of a node among all
the nodes in a tree is called as 'Degree of Tree'
9. Level

In a tree data structure, the root node is said to be at Level 0 and the children of root node are at Level 1 and
the children of the nodes which are at Level 1 will be at Level 2 and so on... In simple words, in a tree each
step from top to bottom is called as a Level and the Level count starts with '0' and incremented by one at each
level (Step).

10. Height

In a tree data structure, the total number of egdes from leaf node to a particular node in the longest path
is called as HEIGHT of that Node.

In a tree, height of the root node is said to be height of the tree. In a tree, height of all leaf nodes is '0'.

11. Depth

In a tree data structure, the total number of egdes from root node to a particular node is called as DEPTH
of that Node.

In a tree, the total number of edges from root node to a leaf node in the longest path is said to be Depth of the
tree.

In simple words, the highest depth of any leaf node in a tree is said to be depth of that tree. In a tree, depth of
the root node is '0'.

12. Path

In a tree data structure, the sequence of Nodes and Edges from one node to another node is called as
PATH between that two Nodes.
Length of a Path is total number of nodes in that path.

In below example the path A - B - E - J has length 4.

13. Sub Tree

Any node of a tree, with all of its descendants is a subtree.

Ancestor of a node:
parent, grand-parent, grand-grand-parent e.t.c.
Example: B,A are the ancestors of node F

Descendent of a node: child, grand child, grand-grand child e.t.c.

Example: E,F,I,K are the descendent of node B

BINARY TREE:

Definition:

A binary tree is a tree such that

 every node has at most 2 children
 each node is labeled as being either a left chilld or a right child

Recursive definition:

A binary tree is empty;

or
It consists of
1. a root node
2. a binary tree, called the left subtree of T
3. a binary tree, called the right subtree of T

A tree with no nodes is called as a null tree.

Binary trees are easy to implement because they have a small, fixed number of child links. Because of this
characteristic, binary trees are the most common types of trees and form the basis of many important data
structures.

Examples:

1. Expression trees
2. Decision trees

Properties of binary trees:

Some of the important properties of a binary tree are as follows:

1. If h = height of a binary tree, then

a) Maximum number of leaves = 2h

b) Maximum number of nodes = 2h+1 - 1

2. If a binary tree contains m nodes at level l, it contains at most 2m nodes at level l + 1.

3. Since a binary tree can contain at most one node at level 0 (the root), it can contain at most
2l node at level l.

4. The total number of edges in a full binary tree with n node is n - 1.

Full Binary Tree AND Complete Binary Tree:

Examples of Full Binary Tree

In a Full Binary, number of leaf nodes is number of internal nodes plus 1
L=I+1
Where L = Number of leaf nodes, I = Number of internal nodes

Examples of Complete Binary Tree :

Binary Trees representation:

1. Array-based Representation; (especially suited for complete and full binary trees.)
2. Linked Representation (Pointer based)

Array-based Representation:

Binary trees can also be stored in arrays, and if the tree is a complete binary tree, this method wastes no space.

In this compact arrangement,

1. if a node has an index i,
 its left child found at index 2i+1
 its right child found at index 2i+2
 its parent (if any) is found at index
floor((i-1)/2)
note: (assuming the root of the tree stored in the array at an index zero).

Consider the following binary tree...

In array representation of binary tree, we use a one dimensional array (1-D Array) to represent a binary tree.
Consider the above example of 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 - 1.

EXAMPLE:
Linked Representation (Pointer based):

Array representation is good for complete binary tree, but it is wasteful for many other binary trees. The
representation suffers from insertion and deletion of node from the middle of the tree, as it requires the
moment of potentially many nodes to reflect the change in level number of this node. To overcome this
difficulty we represent the binary tree in linked representation.

In linked representation each node in a binary tree has three fields, the left child field denoted as LeftChild,
data field denoted as data and the right child field denoted as RightChild.

If any sub-tree is empty then the corresponding pointer’s LeftChild and RightChild will store a NULL value.
If the tree itself is empty the root pointer will store a NULL value.

The advantage of using linked representation of binary tree is that:

 Insertion and deletion involve no data movement and no movement of nodes except the
rearrangement of pointers.

The disadvantages of linked representation of binary tree includes:

 Given a node structure, it is difficult to determine its parent node.
 Memory spaces are wasted for storing NULL pointers for the nodes, which have no subtrees.
The structure definition, node representation empty binary tree is shown in fig-6 and the linked representation
of binary tree using this node structure is given in fig

Binary Tree Traversal Techniques:

A tree traversal is a method of visiting every node in the tree. By visit, we mean that some type of
operation is performed. For example, you may wish to print the contents of the nodes.

There are three common ways to traverse a binary tree:

1. Preorder
2. Inorder
3. Postorder

In the first three traversal methods, the left subtree of a node is traversed before the right subtree.
The difference among them comes from the difference in the time at which a root node is visited.

Recursive Traversal Algorithms:

Inorder Traversal:

In the case of inorder traversal, the root of each subtree is visited after its left subtree
has been traversed but before the traversal of its right subtree begins.

The steps for traversing a binary tree in inorder traversal are:

1. Visit the left subtree, using inorder.

2. Visit the root.
3. Visit the right subtree, using inorder.

The algorithm for inorder traversal is as follows:

void inorder(node *root)

{
if(root == NULL) return;
 inorder(root->lchild);
print root -> data;
inorder(root->rchild);
}

Preorder Traversal:

In a preorder traversal, each root node is visited before its left and right subtrees are
traversed. Preorder search is also called backtracking.

The steps for traversing a binary tree in preorder traversal are:

1. Visit the root.
2. Visit the left subtree, using preorder.
3. Visit the right subtree, using preorder.

The algorithm for preorder traversal is as follows:

void preorder(node *root)

{
if( root == NULL ) return;

print root -> data;

preorder (root -> lchild);
preorder (root -> rchild);

Postorder Traversal:

In a postorder traversal, each root is visited after its left and right subtrees have been traversed.

The steps for traversing a binary tree in postorder traversal are:

1. Visit the left subtree, using postorder.
2. Visit the right subtree, using postorder
3. Visit the root.

The algorithm for postorder traversal is as follows:

void postorder(node *root)

{
if( root == NULL ) return;

postorder (root -> lchild);

postorder (root -> rchild);
print (root -> data);

Example 1:
Traverse the following binary tree in pre, post, inorder and level order.
Example 2:
Traverse the following binary tree in pre, post, inorder and level order.

Example 3:
Traverse the following binary tree in pre, post, inorder and level order.

Example 4:
Traverse the following binary tree in pre, post, inorder and level order.

Expression Trees:
Expression tree is a binary tree, because all of the operations are binary.

The leaves of an expression tree are operands, such as constants or variable names, and the other (non leaf)
nodes contain operators.

It is also possible for a node to have only one child, as is the case with the unary minus operator.

Once an expression tree is constructed we can traverse it in three ways:

 Inorder Traversal
 Preorder Traversal
 Postorder Traversal
Fig shows some more expression trees that represent arithmetic expressions given in infix form.

Fig

An expression tree can be generated for the infix and postfix expressions.

An algorithm to convert a postfix expression into an expression tree is as follows:

1. Read the expression one symbol at a time.

2. If the symbol is an operand, we create a one-node tree and push a pointer to it onto a stack.

3. If the symbol is an operator, we pop pointers to two trees T1 and T2 from the stack (T1 is popped
first) and form a new tree whose root is the operator and whose left and right children point to T2 and
T1 respectively. A pointer to this new tree is then pushed onto the stack.

Example 1:
Construct an expression tree for the postfix expression: a b + c d e + * *

Solution:
The first two symbols are operands, so we create one-node trees and push pointers to them onto a stack.

Next, the operator ‘+’ is read, so two pointers to trees are popped, a new tree is formed, and a pointer to it is
pushed onto the stack.

Next, c, d, and e are read, and for each one–node tree is created and a pointer to the
corresponding tree is pushed onto the stack.
Now the operator ‘+’ is read, so two trees are merged.

Continuing, the operator ‘*’ is read, so we pop two tree pointers and form a new tree with a ‘*’ as
root.

Finally, the last symbol is read, two trees are merged, and a pointer to the final tree is
left on the stack.

For the above tree:

Inorder form of the expression: a + b * c * d + e

Preorder form of the expression: * + a b * c + d e
Postorder form of the expression: a b + c d e + * *

Example 2:

Construct an expression tree for the arithmetic expression:

(A + B * C) – ((D * E + F) / G)

Solution:

First convert the infix expression into postfix notation. Postfix notation of the arithmetic
expression is: A B C * + D E * F + G / -

The first three symbols are operands, so we create one-node trees and pointers to
three nodes pushed onto the stack.

Next, a ‘*’ is read, so two pointers to trees are popped, a new tree is formed, and a pointer to it is pushed onto
the stack.

Next, a ‘+’ is read, so two pointers to trees are popped, a new tree is formed, and a pointer to it is pushed onto
the stack.

Next, D and E are read, and for each one–node tree is created and a pointer to the corresponding tree is
pushed onto the stack.

Continuing, a ‘*’ is read, so we pop two tree pointers and form a new tree with a ‘*’ as root.

Proceeding similar to the previous steps, finally, when the last symbol is read, the expression tree is as
follows:
Binary Search Tree:
A binary search tree is a binary tree.
a. It may be empty.
b. If it is not empty then it satisfies the following properties:

1. Every element has a key and no two elements have the same key.
2. The keys in the left subtree are smaller than the key in the root.
3. The keys in the right subtree are larger than the key in the root.
4. The left and right subtrees are also binary search trees.

Binary Search Tree is a binary tree in which every node contains only smaller values in its left subtree and
only larger values in its right subtree.

The following operations are performed on a binary earch tree...

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

In a binary search tree, the search operation is performed with O(log n) time complexity.

The search operation is performed as follows...

Step 1: Read the search element from the user

Step 2: Compare, the search element with the value of root node in the tree.
Step 3: If both are matching, then display "Given node found" and terminate the function
Step 4: If both are not matching, then check whether search element is smaller or larger than that
node value.
Step 5: If search element is smaller, then continue the search process in left subtree.
Step 6: If search element is larger, then continue the search process in right subtree.
Step 7: Repeat the same until we found exact element or we completed with a leaf node
Step 8: If we reach to the node with search value, then display "Element is found" and terminate the
function.
Step 9: If we reach to a leaf node and it is also not matching, then display "Element not found" and
terminate the function.
Program:

// C function to search a given key in a given BST

struct node* search(struct node *root, int key)

{
// Base Cases: root is null or key is present at root

if (root == NULL || root->key == key)

return root;

if (key > root->key ) // Key is greater than root's key

return search(root->right, key);

else // Key is smaller than root's key

return search(root->left, key);
}

Insertion Operation in BST

In a binary search tree, the insertion operation is performed with O(log n) time complexity. In binary search
tree, new node is always inserted as a leaf node.

The insertion operation is performed as follows...

Step 1: Create a newNode with given value and set its left and right to NULL.

Step 2: Check whether tree is Empty.

Step 3: If the tree is Empty, then set set root to newNode.

Step 4: If the tree is Not Empty, then check whether value of newNode is smaller or
larger than the node (here it is root node).

Step 5: If newNode is smaller than or equal to the node, then move to its left child.
If newNode is larger than the node, then move to its right child.
 Step 6: Repeat the above step until we reach to a leaf node (e.i., reach to NULL).

Step 7: After reaching a leaf node,

a) then isert the newNode as left child if newNode is smaller
or equal to that leaf,
b) otherwise insert it as right child.

EXAMPLE:

Construct a Binary Search Tree by inserting the following sequence of numbers...

10,12,5,4,20,8,7,15 and 13

Program:

#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node *left;
struct node *right;
};

typedef struct node node;

node *root = NULL;

node *getnode( )
{
node *new;
 printf("nEnter data:");
new=(node*)malloc(sizeof(node));
scanf("%d",&new->data);
new->left = NULL;
new->right = NULL;
return new;
}

void insert(node *,node *);

void main()
{
char ch;
while(1)
{
Printf(“ enter node to insert \n”);
node *new;
new = getnode( );
insert( root, new);
printf(“ Do you want to insert one more node , press ‘y’ \n”);
if(ch != ‘y’) break;
}
}

void insert(node *root, node *new )

{

if(root == NULL)
root = new;

else
{
if(new->data < = root->data)
{
if(root->left != NULL)
insert(root->left, new);
else
root->left = new;
}

if(new->data > root->data)

{
if(root->right != NULL)
insert(root->right, new);
else
root->right = new;
}
}
}
Deletion Operation in BST

In a binary search tree, the deletion operation is performed with O(log n) time complexity.

Deleting a node from Binary search tree has follwing three cases...

Case 1: Deleting a Leaf node (A node with no children)

Case 2: Deleting a node with one child

Case 3: Deleting a node with two children

Case 1: Deleting a leaf node

We use the following steps to delete a leaf node from BST...

Step 1: Find the node to be deleted using search operation

Step 2: Delete the node using free function (If it is a leaf) and terminate the function.

Case 2: Deleting a node with one child:

We use the following steps to delete a node with one child from BST...
 Step 1: Find the node to be deleted using search operation

Step 2: If it has only one child, then create a link between its parent and child nodes.

Step 3: Delete the node using free function and terminate the function.

Case 3: Deleting a node with two children:

We use the following steps to delete a node with two children from BST...

Step 1: Find the node to be deleted using search operation

Step 2: If it has two children, then find the largest node in its left subtree (OR)
the smallest node in its right subtree.

Step 3: Swap both deleting node and node which found in above step.

Step 4: Then, check whether deleting node came to case 1 or case 2 else goto steps 2

Step 5: If it comes to case 1, then delete using case 1 logic.

Step 6: If it comes to case 2, then delete using case 2 logic.

Step 7: Repeat the same process until node is deleted from the tree.
/* Given a binary search tree and a key, this function deletes the key and returns the new root */

struct node* deleteNode(struct node* root, int key)

{
// base case
if (root == NULL) return root;

// If the key to be deleted is smaller than the root's key, then it lies in left subtree

if (key < root->key)

root->left = deleteNode(root->left, key);

// If the key to be deleted is greater than the root's key, then it lies in right subtree

else if (key > root->key)

root->right = deleteNode(root->right, key);

// if key is same as root's key, then This is the node to be deleted

else
{
// node with only one child or no child
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}

// node with two children: Get the inorder successor (smallest in the right subtree)

struct node* temp = minValueNode(root->right);

// Copy the inorder successor's content to this node

root->key = temp->key;

// Delete the inorder successor

root->right = deleteNode(root->right, temp->key);
}
return root;
}
AVL Tree
AVL tree is a self balanced binary search tree. That means, an AVL tree is also a binary search tree but it is a
balanced tree.

A binary tree is said to be balanced, if the difference between the hieghts of left and right subtrees of every
node in the tree is either -1, 0 or +1.

In other words, a binary tree is said to be balanced if for every node, height of its children differ by at most
one.

In an AVL tree, every node maintains a extra information known as balance factor.

The AVL tree was introduced in the year of 1962 by G.M. Adelson-Velsky and E.M. Landis.

Definition:

An AVL tree is a balanced binary search tree. In an AVL tree, balance factor of every node is
either -1, 0 or +1.

Balance factor of a node is the difference between the heights of left and right subtrees of that node. The
balance factor of a node is calculated either height of left subtree - height of right subtree (OR) height of
right subtree - height of left subtree.

In the following explanation, we are calculating as follows...

Balance factor = height Of LeftSubtree – height Of RightSubtree

How effective is this? The height of an AVL tree with N nodes never exceeds 1.44 log N and is typically
much closer to log N.
Example:

The above tree is a binary search tree and every node is satisfying balance factor condition. So this tree is said
to be an AVL tree.

NOTE:
Every AVL Tree is a binary search tree but all the Binary Search Trees need not to be AVL trees.

AVL Tree Rotations

In AVL tree, after performing every operation like insertion and deletion we need to check the balance factor
of every node in the tree. If every node satisfies the balance factor condition then we conclude the operation,
otherwise we must make it balanced.

We use rotation operations to make the tree balanced whenever the tree is becoming imbalanced due to any
operation.
Rotation operations are used to make a tree balanced.

Rotation is the process of moving the nodes to either left or right to make tree balanced.

There are four rotations and they are classified into two types.
The following operations are performed on an AVL tree...

1. Search
2. Insertion
3. Deletion

Search Operation in AVL Tree

In an AVL tree, the search operation is performed with O(log n) time complexity. The search operation is
performed similar to Binary search tree search operation.

We use the following steps to search an element in AVL tree...

Step 1: Read the search element from the user

Step 2: Compare, the search element with the value of root node in the tree.
Step 3: If both are matching, then display "Given node found!!!" and terminate the function
Step 4: If both are not matching, then check whether search element is smaller or larger than that node
value.
Step 5: If search element is smaller, then continue the search process in left subtree.
Step 6: If search element is larger, then continue the search process in right subtree.
 Step 7: Repeat the same until we found exact element or we completed with a leaf node
Step 8: If we reach to the node with search value, then display "Element is found" and terminate the
function.
Step 9: If we reach to a leaf node and it is also not matching, then display "Element not found" and
terminate the function.

Insertion Operation in AVL Tree

In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL Tree, new node
is always inserted as a leaf node. The insertion operation is performed as follows...

Step 1: Insert the new element into the tree using Binary Search Tree insertion logic.
Step 2: After insertion, check the Balance Factor of every node.
Step 3: If the Balance Factor of every node is 0 or 1 or -1 then go for next operation.
Step 4: If the Balance Factor of any node is other than 0 or 1 or -1 then tree is said to be imbalanced.
Then perform the suitable Rotation to make it balanced. And go for next operation.

Example:

Construct an AVL Tree by inserting numbers from 1 to 8.

Deletion Operation in AVL Tree

In an AVL Tree, the deletion operation is similar to deletion operation in BST.

But after every deletion operation we need to check with the Balance Factor condition.

If the tree is balanced after deletion then go for next operation otherwise perform the suitable rotation to make
the tree Balanced.