WAP to Find Two Nodes Into Binary Search Tree such That they are equals to given number

Given a binary search tree of n nodes, find two nodes whose sum is equal to a given number k in O(n) time and constant space

Data Structure Used: Binary Search Tree

Algorithm:
1.Convert BST into sorted DLL which Will Take O(N) Time(Check previous Posts Already Coded) you can see here "cslibrary.stanford.edu/109"
2.take find sum into DLL two pointer start,end which points to starting & end position of DLL.
3. start from start->data & end->data , keep checking until we get all the number that sums to
given value as shown
while(ptr1->data < ptr2-> data)
{
if ((ptr1->data + ptr2-> data )>k)
ptr2= ptr2->prev;
else if ((ptr1->data + ptr2-> data )
ptr1= ptr1->next;
else if ((ptr1->data + ptr2-> data ) == k)
{
print_data_of_ptr1_and_ptr2;
ptr2= ptr2->prev;
ptr1= ptr1->next;
}
}
it will take O(N) time


Working Code (Need to Verify getting TLE)??

#include
#include
#include

/* The node type from which both the tree and list are built */
struct node {
int data;
struct node* small;
struct node* large;
};
typedef struct node* Node;



/*
helper function -- given two list nodes, join them
together so the second immediately follow the first.
Sets the .next of the first and the .previous of the second.
*/
static void join(Node a, Node b) {
a->large = b;
b->small = a;
}


/*
helper function -- given two circular doubly linked
lists, append them and return the new list.
*/
static Node append(Node a, Node b) {
Node aLast, bLast;

if (a==NULL) return(b);
if (b==NULL) return(a);

aLast = a->small;
bLast = b->small;

join(aLast, b);
join(bLast, a);

return(a);
}


/*
--Recursion--
Given an ordered binary tree, recursively change it into
a circular doubly linked list which is returned.
*/
static Node treeToList(Node root) {
Node aList, bList;

if (root==NULL) return(NULL);

/* recursively solve subtrees -- leap of faith! */
aList = treeToList(root->small);
bList = treeToList(root->large);

/* Make a length-1 list ouf of the root */
root->small = root;
root->large = root;

/* Append everything together in sorted order */
aList = append(aList, root);
aList = append(aList, bList);

return(aList);


}

/* Create a new node */
static Node newNode(int data) {
Node node = (Node) malloc(sizeof(struct node));
node->data = data;
node->small = NULL;
node->large = NULL;
return(node);
}


/* Add a new node into a tree */
static void treeInsert(Node* rootRef, int data) {
Node root = *rootRef;
if (root == NULL) *rootRef = newNode(data);
else {
if (data <= root->data) treeInsert(&(root->small), data);
else treeInsert(&(root->large), data);
}
}


void findNums(Node head,int k)
{
Node ptr1,ptr2;
ptr1=head;
while(ptr1->large!=NULL)
ptr1=ptr1->large;
ptr2=ptr1->small;

while(ptr1->data < ptr2-> data)
{
if ((ptr1->data + ptr2-> data )>k)
ptr2= ptr2->small;
else if ((ptr1->data + ptr2->data)large;
else if ((ptr1->data + ptr2-> data ) == k)
{
printf("%d %d", ptr1->data,ptr2->data);
ptr2= ptr2->small;
ptr1= ptr1->large;
}
}

}
static void printList(Node head) {
Node current = head;

while(current != NULL) {
printf("%d ", current->data);
current = current->large;
if (current == head) break;
}
printf("\n");
}


/* Demo that the code works */
int main() {
Node root = NULL;
Node head;
treeInsert(&root, 6);
treeInsert(&root, 4);
treeInsert(&root, 2);
treeInsert(&root, 1);
treeInsert(&root, 3);
treeInsert(&root, 5);
treeInsert(&root, 7);

head = treeToList(root);

printList(head); /* prints: 1 2 3 4 5 6 7 */// int sum=9 ;
findNums(head,9);
return(0);
}



Time Complexity O(n)
Space Complexity O(1)
Run Here http://ideone.com/clone/Sf884

2nd Method (Awesome) Because it Doesn't modify The Tree Structure

Algorithm;
Do two inorder traversals, one in the usual (descend to the left
before descendung to the right) direction and the other in the
reversed(descend to the right before descending to the left)
direction. Let u and r be the current nodee of the two traversals,
respectively. If u + r < x, then advance the usual traversal and repeat the comparison. If u + r > x, advance the reverse traversal and
repeat the comparison. If u + r = x, and if u != r, then terminate
with success. If u = r, then terminate with failure.

Busy Will Try ton Code it Asap...:)