EXPRESSION TREE

 EXPRESSION TREE:

Expression Trees

Binary trees are widely used to store algebraic expressions. For example,

consider the algebraic expression given as:

The expression tree is a tree used to represent the various expressions. The tree data structure is used to represent the expressional statements. In this tree, the internal node always denotes the operators.

• The leaf nodes always denote the operands.
• The operations are always performed on these operands.
• The operator present in the depth of the tree is always at the highest priority.i.e least priority operator will on top.
• The operator, which is not much at the depth in the tree, is always at the lowest priority compared to the operators lying at the depth.
• The operand will always present at a depth of the tree; hence it is considered the highest priority among all the operators.

Associativity for operators

• ʌ (power)                                           : Right to Left
• * (multiplication), / (Divison)            :Left to Right
• - (sub), +(Add)                                   : Left to Right

Ex:  Exp = (a – b) + (c * d)

Ex: Given an expression, Exp = ((a + b) – (c * d)) % ((e ^f) / (g – h)), construct the corresponding binary tree.

Ex: Given the binary tree, write down the expression that it represents.

Expression for the above binary tree is 

                 [{(a/b) + (c*d)} ^ {(f % g)/(h – i)}]

solve the expression  a*b /c + e/f  * g + k - x * y

 

TREE Data structure, Binary Tree

 Tree Data Structure is a non-linear data structure in which a collection of elements known as nodes are connected to each other via edges such that there exists exactly one path between any two nodes.

A tree data structure is a hierarchical structure that is used to represent and organize data in a way that is easy to navigate and search. It is a collection of nodes that are connected by edges and has a hierarchical relationship between the nodes. 

The topmost node of the tree is called the root, and the nodes below it are called the child nodes. Each node can have multiple child nodes, and these child nodes can also have their own child nodes, forming a recursive structure.

Terminologies In Tree Data Structure

• Parent Node: The node which is a predecessor of a node is called the parent node of that node. {B} is the parent node of {D, E}.

• Child Node: The node which is the immediate successor of a node is called the child node of that node. Examples: {D, E} are the child nodes of {B}.

• Root Node: The topmost node of a tree or the node which does not have any parent node is called the root node. {A} is the root node of the tree. A non-empty tree must contain exactly one root node and exactly one path from the root to all other nodes of the tree.

• Leaf Node or External Node: The nodes which do not have any child nodes are called leaf nodes. {I, J, K, F, G, H} are the leaf nodes of the tree.

• Ancestor of a Node: Any predecessor nodes on the path of the root to that node are called Ancestors of that node. {A,B} are the ancestor nodes of the node {E}

• Descendant: A node x is a descendant of another node y if and only if y is an ancestor of x.

• Sibling: Children of the same parent node are called siblings. {D,E} are called siblings.

• Level of a node: The count of edges on the path from the root node to that node. The root node has level 0.

• Internal node: A node with at least one child is called Internal Node.

• Neighbor of a Node: Parent or child nodes of that node are called neighbors of that node.

• Subtree: Any node of the tree along with its descendant.

•  Degree Degree of a node is equal to the number of children that a node has.

The degree of a leaf node is zero.

In-degree In-degree of a node is the number of edges arriving at that node.

Out-degree Out-degree of a node is the number of edges leaving that node.

TYPES OF TREES

Trees are of following 6 types:

1. General trees

2. Forests

3. Binary trees

4. Binary search trees

5. Expression trees

6. Tournament trees

Binary trees:

A binary tree is a data structure that is defined as a collection of elements called nodes. In a binary tree, the topmost element is called the root node, and each node has 0, 1, or at the most 2 children. A node that has zero children is called a leaf node or a terminal node. Every node contains a data element, a left pointer which points to the left child, and a right pointer which points to the right child. The root element is pointed by a 'root' pointer. If root = NULL, then it means the tree is empty.

In above Figure shows a binary tree. In the figure, R is the root node and the two trees T1 and T2 are called the left and right sub-trees of R. T1 is said to be the left successor of R. Likewise, T2 is called the right successor of R.

Note that the left sub-tree of the root node consists of the nodes: 2, 4, 5, 8, and 9. Similarly, the right sub-tree of the root node consists of nodes: 3, 6, 7, 10, 11, and 12.

 In the tree, root node 1 has two successors: 2 and 3. Node 2 has two successor nodes: 4 and 5. Node 4 has two successors: 8 and 9. Node 5 has no successor. Node 3 has two successor nodes: 6 and 7. Node 6 has two successors: 10 and 11. Finally, node 7 has only one successor: 12.

 A binary tree is recursive by definition as every node in the tree contains a left sub-tree and a right sub-tree. Even the terminal nodes contain an empty left sub-tree and an empty right sub-tree. Look at Fig above , nodes 5, 8, 9, 10, 11, and 12 have no successors and thus said to have empty sub-trees.

Terminology

Parent If N is any node in T that has left successor S1 and right successor S2, then N is called the parent of S1 and S2. Correspondingly, S1 and S2 are called the left child and the right child of N. Every node other than the root node has a parent.

Level number Every node in the binary tree is assigned a level number (refer  Fig. below). The root node is defined to be at level 0. The left and the right child of the root node have a level number 1. Similarly, every node is at one level higher than its parents. So all child nodes are defined to have level number as parent's level number + 1.

Path A sequence of consecutive edges. For example, in Fig. above, the path from the root node to the node 8 is given as: 1, 2, 4, and 8.

Degree of a node It is equal to the number of children that a node has. The degree of a leaf node is zero. For example, in the tree, degree of node 4 is 2, degree of node 5 is zero and degree of node 7 is 1.

Sibling All nodes that are at the same level and share the same parent are called siblings (brothers). For example, nodes 2 and 3; nodes 4 and 5; nodes 6 and 7; nodes 8 and 9; and nodes 10 and 11 are siblings.

Leaf node A node that has no children is called a leaf node or a terminal node. The leaf nodes in the tree are: 8, 9, 5, 10, 11, and 12.

Similar binary trees Two binary trees T and T ' are said to be similar if both these trees have the same structure. Figure  shows two similar binary trees.

Copies Two binary trees T and T ' are said to be copies if they have similar structure and if they have same content at the corresponding nodes. Figure below shows that T ' is a copy of T.

Edge It is the line connecting a node N to any of its successors. A binary tree of n nodes has exactly n – 1 edges because every node except the root node is connected to its parent via an edge.

Depth The depth of a node N is given as the length of the path from the root R to the node N. The depth of the root node is zero.

Height of a tree It is the total number of nodes on the path from the root node to the deepest node in the tree. A tree with only a root node has a height of 1.

1.     Properties of Binary Tree

·         At each level of i, the maximum number of nodes is 2i.

·         The height of the tree is defined as the longest path from the root node to the leaf node. The tree which is shown above has a height equal to 3. Therefore, the maximum number of nodes at height 3 is equal to (1+2+4+8) = 15. In general, the maximum number of nodes possible at height h is (2⁰ + 2¹ + 2²+….2^h) = 2^h+1 -1.

·         If the number of nodes is minimum, then the height of the tree would be maximum. Conversely, if the number of nodes is maximum, then the height of the tree would be minimum. If there are 'n' number of nodes in the binary tree.

The minimum height can be computed as:

As we know that,

n = 2^h+1 -1

n+1 = 2^h+1

Taking log on both the sides, log2(n+1) = log2(2^h+1)

log2(n+1) = h+1

h = log2(n+1) – 1

 

The maximum height can be computed as:

As we know that,

n = h+1

h= n-1

 

In-degree/out-degree of a node It is the number of edges arriving at a node. The root node is the only node that has an in-degree equal to zero. Similarly, out-degree of a node is the number of edges leaving that node.

Binary trees are commonly used to implement binary search trees, expression trees, tournament trees, and binary heaps.

Full/ proper/ strict Binary tree

The full binary tree is also known as a strict binary tree. The tree can only be considered as the full binary tree if each node must contain either 0 or 2 children. The full binary tree can also be defined as the tree in which each node must contain 2 children except the leaf nodes.

Let's look at the simple example of the Full Binary tree. 

In the above tree, we can observe that each node is either containing zero or two children; therefore, it is a Full Binary tree.

Properties of Full Binary Tree

The number of leaf nodes is equal to the number of internal nodes plus 1. In the above example, the number of internal nodes is 5; therefore, the number of leaf nodes is equal to 6.

The maximum number of nodes is the same as the number of nodes in the binary tree, i.e., 2^h+1 -1. o The minimum number of nodes in the full binary tree is 2*h-1.

The minimum height of the full binary tree is log2(n+1) - 1.

The maximum height of the full binary tree can be computed as:

n= 2*h - 1

n+1 = 2*h

h = n+1/2

Complete Binary Trees

• A complete binary tree is a binary tree that satisfies two properties. First, in a complete binary tree, every level, except possibly the last, is completely filled. 
• Second, all nodes appear as far left as possible. In a complete binary tree, the nodes should be added from the left.

The above tree is a complete binary tree because all the nodes are completely filled, and all the nodes in the last level are added at the left first.

Properties of Complete Binary Tree

• The maximum number of nodes in complete binary tree is 2^h+1 - 1.
• The minimum number of nodes in complete binary tree is 2^h.
• The minimum height of a complete binary tree is log₂(n+1) - 1.

Representation of Binary Tree

Linked representation of binary trees In the linked representation of a binary tree, every node will have three parts: the data element, a pointer to the left node, and a pointer to the right node.

So in C, the binary tree is built with a node type given below.

struct node {

struct node *left;

int data;

struct node *right;

};

 linked representation of binary tree

                                                  

Each node in a Binary Tree has three parts:

• Data
• Pointer to the left child
• Pointer to the right child

Syntax to declare a Node of Binary Tree

// Structure of each node of the tree. 
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};


struct Node* newNode(int item) {
    struct Node* temp = 
       (struct Node*)malloc(sizeof(struct Node));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

Sequential representation of binary trees 

Sequential representation of trees is done using single or one-dimensional arrays. Though it is the simplest technique for memory representation, it is inefficient as it requires a lot of memory space.

Binary tree and its sequential representation

**************************************

TRAVERSING A BINARY TREE

Traversal is a common operation performed on data structures. It is the process in which each and every element present in a data structure is "visited" (or accessed) at least once. This may be done to display all of the elements or to perform an operation on all of the elements.

Tree Traversal refers to the process of visiting or accessing each node of the tree exactly once in a certain order. Tree traversal algorithms help us to visit and process all the nodes of the tree. Since tree is not a linear data structure, there are multiple nodes which we can visit after visiting a certain node. There are multiple tree traversal techniques which decide the order in which the nodes of the tree are to be visited.

Tree Traversal Techniques:

A Tree Data Structure can be traversed in following ways:

• Depth First Search or DFS

• Inorder Traversal

• Preorder Traversal

• Postorder Traversal

• Level Order Traversal or Breadth First Search or BFS

Inorder Traversal:

Inorder traversal visits the node in the order:

 Left -> Root -> Right

Algorithm for Inorder Traversal:

Inorder(tree)

• Traverse the left subtree, i.e., call Inorder(left->subtree)

• Visit the root.

• Traverse the right subtree, i.e., call Inorder(right->subtree)

Uses of Inorder Traversal:

• In the case of binary search trees (BST), Inorder traversal gives nodes in non-decreasing order.

• To get nodes of BST in non-increasing order, a variation of Inorder traversal where Inorder traversal is reversed can be used.

• Inorder traversal can be used to evaluate arithmetic expressions stored in expression trees.

******************************

Preorder Traversal:

Preorder traversal visits the node in the order: 

Root -> Left -> Right

Algorithm for Preorder Traversal:

Preorder(tree)

• Visit the root.

• Traverse the left subtree, i.e., call Preorder(left->subtree)

• Traverse the right subtree, i.e., call Preorder(right->subtree)

Uses of Preorder Traversal:

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

• Preorder traversal is also used to get prefix expressions on an expression tree.

 ***********************************************

Postorder Traversal:

Postorder traversal visits the node in the order: 

Left -> Right -> Root

Algorithm for Postorder Traversal:

Algorithm Postorder(tree)

• Traverse the left subtree, i.e., call Postorder(left->subtree)

• Traverse the right subtree, i.e., call Postorder(right->subtree)

• Visit the root

Uses of Postorder Traversal:

• Postorder traversal is used to delete the tree. 

• Postorder traversal is also useful to get the postfix expression of an expression tree.

• Postorder traversal can help in garbage collection algorithms, particularly in systems where manual memory management is used.

************************************

Level Order Traversal :

Level Order Traversal visits all nodes present in the same level completely before visiting the next level.

Algorithm for Level Order Traversal:

LevelOrder(tree)

• Create an empty queue Q

• Enqueue the root node of the tree to Q

• Loop while Q is not empty

• Dequeue a node from Q and visit it

• Enqueue the left child of the dequeued node if it exists

• Enqueue the right child of the dequeued node if it exists

Printing the value of each node as we "visit" it, we get the following output level order 

    A B W X S T C E M P N H

Uses of Level Order:

• Level Order Traversal is mainly used as Breadth First Search to search or process nodes level-by-level.

• Level Order traversal is also used for Tree Serialization and Deserialization .

SORTING (Merge Sort, Quick Sort, Heap sor )

 SORTING (  Merge Sort, Quick Sort, Heap sort )

 Merge Sort:

Merge sort is the sorting technique that follows the divide, conquer, and combine algorithmic paradigm.

Divide means partitioning the n-element array to be sorted into two sub-arrays of n/2 elements. If A is an array containing zero or one element, then it is already sorted. However, if there are more elements in the array, divide A into two sub-arrays, A1 and A2, each containing about half of the elements of A.

Conquer means sorting the two sub-arrays recursively using merge sort.

Combine means merging the two sorted sub-arrays of size n/2 to produce the sorted array of n elements.

The basic steps of a merge sort algorithm are as follows:

• If the array is of length 0 or 1, then it is already sorted.
• Otherwise, divide the unsorted array into two sub-arrays of about half the size.
• Use merge sort algorithm recursively to sort each sub-array.
• Merge the two sub-arrays to form a single sorted list.

 It is one of the most popular and efficient sorting algorithm. It divides the given list into two equal halves, calls itself for the two halves and then merges the two sorted halves. We have to define the merge() function to perform the merging.

Algorithm

In the following algorithm, arr is the given array, beg is the starting element, and end is the last element of the array.

The important part of the merge sort is the MERGE function. This function performs the merging of two sorted sub-arrays that are A[beg…mid] and A[mid+1…end], to build one sorted array A[beg…end]. So, the inputs of the MERGE function are A[], beg, mid, and end.

The merge sort algorithm  uses a function merge which combines the sub-arrays to form a sorted array. While the merge sort algorithm recursively divides the list into smaller lists, the merge algorithm conquers the list to sort the elements in individual lists. Finally, the smaller lists are merged to form one list.

The implementation of the MERGE function is given as follows:

To understand the merge algorithm, consider the figure below which shows how we merge two lists to form one list. For ease of understanding, we have taken two sub-lists each containing four elements. The same concept can be utilized to merge four sub-lists containing two elements, or eight sub-lists having one element each.

Compare ARR[I] and ARR[J], the smaller of the two is placed in TEMP at the location specified by INDEX and subsequently the value I or J is incremented.

When I is greater than MID, copy the remaining elements of the right sub-array in TEMP.

Write a program to implement merge sort.

#include <stdio.h>

void merge(int a[], int, int, int);

void merge_sort(int a[],int, int);

void main()

{

int arr[size], i, n;

printf("\n Enter the number of elements in the array : ");

scanf("%d", &n);

printf("\n Enter the elements of the array: ");

for(i=0;i<n;i++)

{

scanf("%d", &arr[i]);

}

merge_sort(arr, 0, n-1);

printf("\n The sorted array is: \n");

for(i=0;i<n;i++)

printf(" %d\t", arr[i]);

}

void merge(int arr[], int beg, int mid, int end)

{

int i=beg, j=mid+1, index=beg, temp[size], k;

while((i<=mid) && (j<=end))

{

if(arr[i] < arr[ j ])

{

temp[index] = arr[ i ];

i++;

}

else

{

temp[index] = arr[ j ];

j++;

}

index++;

}

if(i > mid)

{

while(j<=end)

{

temp[index] = arr[j];

j++;

index++;

}

}

else

{

while(i<=mid)

{

temp[index] = arr[i];

i++;

index++;

}

}

for(k=beg;k<index;k++)

arr[k] = temp[k];

}

void merge_sort(int arr[], int beg, int end)

{

int mid;

if(beg<end)

{

mid = (beg+end)/2;

merge_sort(arr, beg, mid);

merge_sort(arr, mid+1, end);

merge(arr, beg, mid, end);

}

}

Merge sort complexity

• Best Case Complexity - It occurs when there is no sorting required, i.e. the array is already sorted. The best-case time complexity of merge sort is O(n*logn).
• Average Case Complexity - It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of merge sort is O(n*logn).
• Worst Case Complexity - It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of merge sort is O(n*logn).

*************************