CareerCup

What do you think if I use hash-maps as follow:

use preorder traversal:

if(root->data < x)
{
if(x - root->data is present)
{
hash[x - root->data] = root->data;
}
else
{
hash[root->data] = -1;
}
}


in simple way create a hash having sum of key & value pair is equal to given x

If extra space is allowed then read the BST in to an array in inorder and then find the elements.
If extra space is not allowed then i think O(N) solution is not possible.

Convert the BST into a doubly linked list and then simply use the concept of finding two elements from an array having a sum equal to x. Conversion doesn't require any extra space and is in O(n) time.

Yes both ways are possible from doubly to bst and vice versa. Codes are available easily upon searching on google.

I think that the following shall work:

bool FindPair (Node node, int x, IDictionary<int, int> dic)
{
if (node == null)
return false;
if (dic.Keys.Contains(node.Data))
return true;
dic[x-node.data]=node.Data;
if (node.Data >= x)
return FindPair(node.Left,x,dic);
else
return FindPair(node.Left,x,dic) || FindPair(node.Right,x,dic);
}

how about for every node in the tree
call FindElement(target-elementValue) ---O(log n)

for n nodes....we can complete all the pairs of nodes in n logn

works for negative numbers too

@anonymous good solution... but how u ppl think recursively... gr88 :)

yes its really a nie one solution that first converrt a bst into the dubly linked list and then again converting the doubly linked llist into the
code for converting bst to sorted doubly linked list without taking extra space
:
void BsttoDll(struct node *r,struct node **head,struct node *prev)
{
if(!r)
return;
BsttoDll(r->left,head,prev);
if(!head)
{
*head=r;
}
else
{
prev->right=r;
}
r->left=prev;
prev=r;
BsttoDll(r->right,head,prev);
}
in second step just take the two pointers one at the start node and one at the end node and start traversing it in o(n)

void Pairofnoes(struct node *head)
{
struct node *last;
last=head;
while(last->right)
last=last->right;

start=head;

while(start!=head)
{
if(start->info+last->info==key)
{printf("the pair of nodes (%d,%d)\n",start->info,last->info);
start=start->right;
last=last->left;
}
if(start->info+last->info< key)
start=start->right;
else
}
last=last->left;
}
}}

in the 3rd step which is optional thats is if asked that the bst should be remain as it is so just again convert the doubly linked list into the bst which ids really easy and again taking no any further space and just a o(n) time complexitry algorithm
code:
struct node DLLtoBSt(struct node* head)
{
if(!r)
return NULL;
else
{
struct node *x;
struct node *y;
x=y=head;
while(y->next && y->next->next)
{
x=x->right;
y=y->right->right;
}
if(x->left)
{
x->left->right=NULL;
x->left=DlltoBST(x);
}
x->right->left=NULL;
x->right=DLLtoBST(x->right);
}

return x;
}

hence all the seps takes in o(n) time :)

I am not sure how can we find the pair which sums up to X in an array in O(N). Can someone highlight? For every number A, we will need to search for (X-A) in the array to see if it can sum up to X or not - we can use binary search to optimize, but we'll need to search nevertheless.

The above leads to a simple algorithm, that in the given BST, do a pre-order traversal - for each node of value Y, search for its complement (X-Y) in the tree. The problem will be solved when one such pair is found.

We'll need to take care of special condition where X = 2Y and we can end up searching Y as complement of itself.

The complexity of algo is Nlg(N)

do the inorder traversal and find two element as x

node *head=root
void inorder(node *root)
{int k=0;
 if(root!=NULL)
  { inorder(root->left);
    k=search(head,x-root->data);
    if(k==1)
      {print ("found");
       return ;
      }
    inorder(root->right);
  }
}

Algorithm:
1. Convert the BST into a circular doubly linked list.

2. The list's head(say h) has its left pointer pointing to the last node. Remember the left pointer in a node temp.

3. Break the circle by changing left pointer for first node and right ptr of tail node
temp=h->left;(currently last node)
h->left=NULL;
temp->right=NULL;
Note that it is easier to convert into a circular doubly list(head's left always points to last node) and then break the circle rather than having to maintain head and tail pointer(especially while forming the list).

4. Now maintain 2 pointers start and end pointing to first and last node of the doubly linked list.
5.while(start->value<end->value)
{
if(start->val+end->val==sum)
{
print the two node values
start=start->right;
end=end->left
}
else if(start->val+end->val>sum)
end=end->left;
else
start=start->right;
}

Algorithm:
1. Convert the BST into a circular doubly linked list.

2. The list's head(say h) has its left pointer pointing to the last node. Remember the left pointer in a node temp.

3. Break the circle by changing left pointer for first node and right ptr of tail node
temp=h->left;(currently last node)
h->left=NULL;
temp->right=NULL;
Note that it is easier to convert into a circular doubly list(head's left always points to last node) and then break the circle rather than having to maintain head and tail pointer(especially while forming the list).

4. Now maintain 2 pointers start and end pointing to first and last node of the doubly linked list.
5.while(start->value<end->value)
{
if(start->val+end->val==sum)
{
print the two node values
start=start->right;
end=end->left
}
else if(start->val+end->val>sum)
end=end->left;
else
start=start->right;
}

Complexity: Transforming BST to DLL = O(N)
Finding the pair that sum up=O(N). Just one scan of the entire list
Total Complexity= O(N)