AVL TREE

 AVL TREE

 

The first type of self-balancing binary search tree to be invented is the AVL tree. The name AVL tree is coined after its inventor's names − Adelson-Velsky and Landis.

In AVL trees, the difference between the heights of left and right subtrees, known as the Balance Factor, must be at most one. Once the difference exceeds one, the tree automatically executes the balancing algorithm until the difference becomes one again.

In an AVL tree, the heights of the two sub-trees of a node may differ by at most one. Due to this  property, the AVL tree is also known as a height-balanced tree.

AVL trees are self-balancing, which means that the tree height is kept to a minimum so that a very fast runtime is guaranteed for searching, inserting and deleting nodes, with time complexity  O(log n).

In its structure, it stores an additional variable called the BalanceFactor. Thus, every node has a balance factor associated with it. 

The balance factor of a node is calculated by subtracting the height of its right sub-tree from the height of its left sub-tree. A binary search tree in which every node has a balance factor of –1, 0, or 1 is said to be height balanced. A node with any other balance factor is considered to be unbalanced and requires rebalancing of the tree.

Balance factor = Height (left sub-tree) – Height (right sub-tree)

• ·   If the balance factor of a node is 1, then it means that the left sub-tree of the tree is one level higher than that of the right sub-tree. Such a tree is therefore called as a left-heavy tree.
• ·  If the balance factor of a node is 0, then it means that the height of the left sub-tree (longest path in the left sub-tree) is equal to the height of the right sub-tree.(balanced AVL tree.
  )
• ·   If the balance factor of a node is –1, then it means that the left sub-tree of the tree is one level lower than that of the right sub-tree. Such a tree is therefore called as a right-heavy tree.

Look at Fig a Left-heavy AVL tree.  Note that the nodes 18, 39, 54, and 72 have no children, so their balance factor = 0. Node 27 has one left child and zero right child. So, the height of left sub-tree = 1, whereas the height of right sub-tree = 0. Thus, its balance factor = 1. Look at node 36, it has a left sub-tree with height = 2, whereas the height of right sub-tree = 1. Thus, its balance factor = 2 – 1 = 1. Similarly, the balance factor of node 45 = 3 – 2 =1; and node 63 has a balance factor of 0 (1 – 1).

Look at Fig b right-heavy AVL tree.  Note that the nodes 70,54,39, and 27 have no children, so their balance factor = 0. Node 72 has one left child and zero right child. So, the height of left sub-tree = 1, whereas the height of right sub-tree = 0. Thus, its balance factor = 1.

 Look at node 63 it has a left sub-tree with height = 1, whereas the height of right sub-tree = 2. Thus, its balance factor = 1 – 2 = -1. Similarly, the balance factor of node 45 = 2 – 3 = -1; and node 36 has a balance factor of 0 (1 – 1).

Look at Fig C. balanced AVL tree.

AVL Rotations

We perform rotation in AVL tree only in case if Balance Factor is other than -1, 0, and 1. There are basically four types of rotations which are as follows:

The Four "out-of-balance" Cases

When the balance factor of just one node is less than -1, or more than 1, the tree is regarded as out of balance, and a rotation is needed to restore balance.

There are four different ways an AVL Tree can be out of balance, and each of these cases require a different rotation operation.

Case	Description	Rotation to Restore Balance
Left-Left (LL)	The unbalanced node and its left child node are both left-heavy.	A single right rotation.
Right-Right (RR)	The unbalanced node and its right child node are both right-heavy.	A single left rotation.
Left-Right (LR)	The unbalanced node is left heavy, and its left child node is right heavy.	First do a left rotation on the left child node, then do a right rotation on the unbalanced node.
Right-Left (RL)	The unbalanced node is right heavy, and its right child node is left heavy.	First do a right rotation on the right child node, then do a left rotation on the unbalanced node.

The first two rotations LL and RR are single rotations and the next two rotations LR and RL are double rotations. For a tree to be unbalanced, minimum height must be at least 2, Let us understand each rotation

1. LL Rotation

When a node is added into the right subtree of the right subtree, if the tree gets out of balance, we do a single left rotation.

In above example, node A has balance factor -2 because a node C is inserted in the right subtree of A right subtree. We perform the LL rotation on the edge below A.

2. RR Rotation

If a node is added to the left subtree of the left subtree, the AVL tree may get out of balance, we do a single right rotation

In above example, node C has balance factor 2 because a node A is inserted in the left subtree of C left subtree. We perform the RR rotation on the edge below A.

Left-Right Rotation:

A left-right rotation is a combination in which first left rotation takes place after that right rotation executes.

1. Node B has been inserted into the right subtree of A the left subtree of C, because of which C has become an unbalanced node having balance factor 2. This case is L R rotation where: Inserted node is in the right subtree of left subtree of C
2. As LR rotation = LL+RR rotation, hence LL on subtree rooted at A is performed first. By doing LL rotation, node A, has become the left subtree of B.
3. After performing LL rotation, node C is still unbalanced, i.e., having balance factor 2, as inserted node A is in the left of left of C
4. Now we perform RR rotation on full tree, i.e. on node C. node C has now become the right subtree of node B, A is left subtree of B. 
5. Balance factor of each node is now either -1, 0, or 1, i.e. BST is balanced now.

Right-Left Rotation:

A right-left rotation is a combination in which first right rotation takes place after that left rotation executes.

1. Node B has been inserted into the left subtree of C the right subtree of A, because of which A has become an unbalanced node having balance factor - 2. This case is RL rotation where: Inserted node is in the left subtree of right subtree of A
2. As RL rotation = RR rotation + LL rotation, hence, RR on subtree rooted at C is performed first. By doing RR rotation, node C has become the right subtree of B.
3. After performing RR rotation, node A is still unbalanced, i.e. having balance factor -2, which is because of the right-subtree of the right-subtree node A.
4. Now we perform LL rotation on full tree, i.e. on node A. node C has now become the right subtree of node B, and node A has become the left subtree of B.
5. Balance factor of each node is now either -1, 0, or 1, i.e. BST is balanced now.

Advantages of AVL Tree:

AVL trees can self-balance themselves and therefore provides time complexity as O(Log n) for search, insert and delete.

It is a BST only (with balancing), so items can be traversed in sorted order.

Since the balancing rules are strict compared to Red Black Tree, AVL trees in general have relatively less height and hence the search is faster.

AVL tree is relatively less complex to understand and implement compared to Red Black Trees.

Disadvantages of AVL Tree:

It is difficult to implement compared to normal BST and easier compared to Red Black

Less used compared to Red-Black trees.

Due to its rather strict balance, AVL trees provide complicated insertion and removal operations as more rotations are performed.

Applications of AVL Tree:

AVL Tree is used as a first example self balancing BST in teaching DSA as it is easier to understand and implement compared to Red Black

Applications, where insertions and deletions are less common but frequent data lookups along with other operations of BST like sorted traversal, floor, ceil, min and max.

Red Black tree is more commonly implemented in language libraries like map in C++, set in C++, TreeMap in Java and TreeSet in Java.

AVL Trees can be used in a real time environment where predictable and consistent performance is required.

Step through the building of an AVL Tree in the animation below to see how the balance factors are updated, and how rotation operations are done when required to restore the balance.

Binary Search Trees(BST)

 Binary Search Trees (BST):

A binary search tree, also known as an ordered binary tree. In a binary search tree, all the nodes in the left sub-tree have a value less than that of the root node. Correspondingly, all the nodes in the right sub-tree have a value either equal to or greater than the root node. The same rule is applicable to every sub-tree in the tree.

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

Similarly, we can see the left child of root node is greater than its left child and smaller than its right child. So, it also satisfies the property of binary search tree. Therefore, we can say that the tree in the above image is a binary search tree.

In the above tree, the value of root node is 40, which is greater than its left child 30 but smaller than right child of 30, i.e., 55. So, the above tree does not satisfy the property of Binary search tree. Therefore, the above tree is not a binary search tree.

Example of creating a binary search tree

Example : State whether the binary trees in below Fig. are binary search trees or not.

Example : Now, let's see the creation of binary search tree using an example.

Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50

• First, we have to insert 45 into the tree as the root of the tree.
• Then, read the next element; if it is smaller than the root node, insert it as the root of the left subtree, and move to the next element.
• Otherwise, if the element is larger than the root node, then insert it as the root of the right subtree.

Now, let's see the process of creating the Binary search tree using the given data element. The process of creating the BST is shown below 

Example : Create a binary search tree using the following data elements: 45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67, 81

OPERATIONS ON BINARY SEARCH TREES

Searching for a Node in a Binary Search Tree:

The search function is used to find whether a given value is present in the tree or not. The searching process begins at the root node. 

The function first checks if the binary search tree is empty. If it is empty, then the value we are searching for is not present in the tree. So, the search algorithm terminates by displaying an appropriate message. 

However, if there are nodes in the tree, then the search function checks to see if the key value of the current node is equal to the value to be searched.

If not, it checks if the value to be searched for is less than the value of the current node, in which case it should be recursively called on the left child node. 

In case the value is greater than the value of the current node, it should be recursively called on the right child node.

See the illustration below for a better understanding:

Algorithm to search for a given value in a binary search tree

Insert a value in a Binary Search Tree:

A new key is always inserted at the leaf by maintaining the property of the binary search tree. We start searching for a key from the root until we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node. The below steps are followed while we try to insert a node into a binary search tree:

 

v  Initilize the current node (say, currNode or node) with root node

v  Compare the key with the current node.

v  Move left if the key is less than or equal to the current node value.

v  Move right if the key is greater than current node value.

v  Repeat steps 2 and 3 until you reach a leaf node.

v  Attach the new key as a left or right child based on the comparison with the leaf node’s value.

Follow the below illustration for a better understanding:

Algorithm to insert a given value in a binary search tree

Deleting a Node from a Binary Search Tree:

Delete function is used to delete the specified node from a binary search tree. However, we must delete a node from a binary search tree so that the property of the binary search tree doesn't violate. There are three situations in which a node can be deleted from a binary search tree.

Case 1: Deleting a Node that has No Children

It is the simplest case, in this case, replace the leaf node with the NULL and simple free the allocated space.

In the following image, we are deleting the node 85, since the node is a leaf node, therefore the node will be replaced with NULL and allocated space will be freed.

Case 2: Deleting a Node with One Child

In this case, the node’s child is set as the child of the node’s parent (i.e replace the node with its child).

if the node is the left child of its parent, the node’s child becomes the left child of the node’s parent. Correspondingly, if the node is the right child of its parent, the node’s child becomes the right child of the node’s parent.

In the following image, the node 12 is to be deleted. It has only one child. The node will be replaced with its child node and the replaced node 12 (which is now leaf node) will simply be deleted.

Case 3: Deleting a Node with Two Children

this case, replace the node’s value with its in-order predecessor (largest value in the left sub-tree) or in-order successor (smallest value in the right sub-tree).

Deleting node 56 from the given binary search tree  by replacing node 56 with its in-order predecessor

This deletion could also be handled by replacing node 56 with its in-order successor

ex: In the following image, the node 50 is to be deleted which is the root node of the tree. 

The in-order traversal of the tree given below 6, 25, 30, 50, 52, 60, 70, 75.

replace 50 with its in-order successor 52. Now, 50 will be moved to the leaf of the tree, which will simply be deleted.

Delete (TREE, ITEM)

o         Step 1: IF TREE = NULL

   Write "item not found in the tree" ELSE IF ITEM < TREE -> DATA

  Delete(TREE->LEFT, ITEM)

  ELSE IF ITEM > TREE -> DATA

   Delete(TREE -> RIGHT, ITEM)

  ELSE IF TREE -> LEFT AND TREE -> RIGHT

  SET TEMP = findLargestNode(TREE -> LEFT)

  SET TREE -> DATA = TEMP -> DATA

   Delete(TREE -> LEFT, TEMP -> DATA)

                 ELSE

   SET TEMP = TREE

   IF TREE -> LEFT = NULL AND TREE -> RIGHT = NULL

   SET TREE = NULL

  ELSE IF TREE -> LEFT != NULL

  SET TREE = TREE -> LEFT

  ELSE

    SET TREE = TREE -> RIGHT

  [END OF IF]

  FREE TEMP

[END OF IF]

o             Step 2: END

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 .