Simple C Program to get the kth node from last in a linked list

This can be done in single traversal using two pointers . First move to the kth node from first and point it using temp pointer . Point the head node using another pointer called kthnodefromlast .Now Move the temp pointer and kthnodefromlast to next node till temp node reaches the end of the linked list.

Example:

 1->2->3->4->5->6->7->NULL

 For the above linked list kth(k=3) node from last is 5.

 Code:(in C)
Time Complexity : O(n)
Space Complexity: O(1)

 Please let me know if you have any questions .

C Program to swap kth node from first and kth node from last in a Linked List

Consider you have the following linked list and you want to swap second node from first and second node from last .

The steps are given below .

     1)Get the size of the linked list . If the size is less than k you can't swap the element . And in the above linked list if k value is 3 you dont need to swap the element .
     2)The two pointers kthnodefromfirst and kthnodefromlast used to point the nodes that we need to swap and its previous nodes are pointed using previous1,previous2.
     3)swap the two nodes . And while swapping you need to check whether you are swapping the head or not . Its one of the important test case .

Code:(in C)

Time Complexity : O(n)
Space Complexity: O(1)

Please let me know if you have any questions .

Simple C Program to check whether the given Binary Tree is Binary Search Tree or not

This can be done in many ways . The simplest way is by using the Inorder Traversal . If we traverse a binary search tree using inorder traversal all the elements are in sorted order .

For the above binary search tree Inorder traversal is

 1  2  3  4  5  6  7

In the following code flag is used like a boolean varible . In the Inorder traversal if the elements are not in sorted order flag is set to 0 . The variable 'min' is used to store the previous value in inorder traversal . Initially it is assigned to the mininum integer value possible which is -32768.

Code :(in C)

Please let me know if you have any questions .