data structures using if(prev !nullprintf(% "prev->val)ptr prev->rightwhile(prev !null &prev->threadprintf(% "ptr->val)prev ptrptr ptr->right}while(ptr !null)void main(/struct tree *root=nullclrscr()create_threaded_tree()printf(\ the in-order traversal of the tree can be given as ")inorder(root)getch()output enter the elementspress - to terminate enter the next element enter the next element enter the next element enter the next element enter the next element - the in-order traversal of the tree can be given as avl trees avl tree is self-balancing binary search tree invented by adelson-velsky and landis in the tree is named avl in honour of its inventors in an avl treethe heights of the two sub-trees of node may differ by at most one due to this propertythe avl tree is also known as height-balanced tree the key advantage of using an avl tree is that it takes (log ntime to perform searchinsertand delete operations in an average case as well as the worst case because the height of the tree is limited to (log nthe structure of an avl tree is the same as that of binary search tree but with little difference in its structureit stores an additional variable called the balancefactor thusevery node has balance factor associated with it the balance factor of node is calculated by subtracting the height of its right sub-tree from the height of its left sub-tree binary search tree in which every node has balance factor of - or is said to be height balanced node with any other balance factor is considered to be unbalanced and requires rebalancing of the tree balance factor height (left sub-treeheight (right sub-treeif the balance factor of node is then it means that the left sub-tree of the tree is one level higher than that of the right sub-tree such tree is therefore called as left-heavy tree if the balance factor of node is then it means that the height of the left sub-tree (longest path in the left sub-treeis equal to the height of the right sub-tree if the balance factor of node is - then it means that the left sub-tree of the tree is one level lower than that of the right sub-tree such tree is therefore called as right-heavy tree look at fig note that the nodes and have no childrenso their balance factor node has one left child and zero right child sothe height of left sub-tree whereas the height of right sub-tree thusits balance factor look at node it has left