Vinay's Blog Rants

                       Threaded Binary Trees. Node Format In Threaded Binary Trees: LTAG LEFT DATA RIGHT RTAG ⇒For Threaded Binary tree: if Ltag==0 ⇒ left points to inorder predecessor. if Ltag==1 ⇒ left points to left child. if Rtag==0 ⇒ right  points to inorder sucessor. if Rtag==1 ⇒ right points to right child. Find in-order sucessor in-order threaded binary tree: psuedo code to find in-order successor: threaded BT * p; if( rtag==0 ) {     successor is p->right; } else {    p=p->right;    while( p->ltag==1 )         p=p->left; } return p; Diagram:

Arrays, linked lists ,stacks qeues - Linear Datastructures Trees - Hierarchical DataStructures ----------------------------------------------------------------------------------------- WHY LINKED LISTS ??? Arrays can be used to store linear data of similar types, but arrays have following limitations. 1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage. 2) Inserting a new element in an array of elements is expensive, because room has to be created for the new elements and to create room existing elements have to shifted. Advantages over arrays 1) Dynamic size 2) Ease of insertion/deletion Drawbacks: 1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists. 2) Extra memory space for a pointer is required w...

There are different types of sorting techniques available they are:- A)Internal Sorting b) External Sorting (Sorting algorithms that use external memory) *********************** PART-1 *********************** 1)Selection sort 2)Bubble sort 3)Insertion sort 4)Quick sort - (Divide and Conquer) 5)Merge sort - (Divide and Conquer) 6)Heap sort - (Not divide and conquer) *********************** PART- 2(Linear Sorting Algorithms) *********************** in earllier sections we have seen many examples on comparison based sorting algorithms. among them the best comparison- based sorting has the complexity O(nLogn). This linear sorting algorithms improve time complexity of these sorting algorithms. We can improve the complexity up to O(n). Few examples of Linear sorting algorithms are shown below. 1)Counting sort 2)Bucket sort 3)Radix sort ************************ Good resource for comparing complexities: http://bigocheatsheet.com/ ----------------------------...