Given a BST and integer value K. Find all pairs of nodes (x,y), such that
x-data + y-data = K
Time O(n)
Can someone provide a pseudocode/code to solve this using the concept of
inorder and reverse inorder traversal of BST?
PS: please don't post other solutions for this, I know this can be solved
If we dont want the tree back, we can convert the BST to DLL and do the
job..
On Mon, Jul 11, 2011 at 3:01 PM, aanchal goyal goyal.aanch...@gmail.comwrote:
Given a BST and integer value K. Find all pairs of nodes (x,y), such that
x-data + y-data = K
Time O(n)
Can someone provide a
we should not deform the tree.
- converting into dll and solving.
- doing inorder and hashing
- doing inorder and saving in array
All above solutions I know, so dont post them,
i dont know how to solve this using inorder and reverse inorder approach..
On Mon, Jul 11, 2011 at 3:13 PM, Piyush Sinha
Ok lets see.
1-Traverse a pointer right down to the leftmost element,i.e.the
shortest,say small
2-traverse a pointer left down to the rightmost element i.e.the largest.say
large
while(small!=large)
3-Compare their sum.If sumk set large to its successor in reverse
inorder.(I am not sure if u meant
We need all pairs.
Best Regards,
T V Thirumala Reddy
On Mon, Jul 11, 2011 at 3:56 PM, saurabh singh saurab...@gmail.com wrote:
Ok lets see.
1-Traverse a pointer right down to the leftmost element,i.e.the
shortest,say small
2-traverse a pointer left down to the rightmost element i.e.the
what is the complexity of your alg?
Best Regards,
T V Thirumala Reddy
On Mon, Jul 11, 2011 at 4:02 PM, TIRU REDDY tiru...@gmail.com wrote:
We need all pairs.
Best Regards,
T V Thirumala Reddy
On Mon, Jul 11, 2011 at 3:56 PM, saurabh singh saurab...@gmail.comwrote:
Ok lets see.
Finding the smallest node-o(logn)
Finding the largest node-o(logn)
Finding the Successor.(o(1) (depends if u have the parent pointer in the
tree implementation))
worst case traversal-o(n)
COmplexity o(logn)+o(logn)+o(n*1)=o(n)
correct me if I am wrong.I was never good with calculating complexity,
@saurabh:
finding succesor may not be O(1)... it can be O(logn)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
@AanchalI think my following algo will work..its a modification of
Morris traversal...check if you can find any bug in it...I have tried my
best to make it error free..For further details regarding Morris traversal,
check out http://geeksforgeeks.org/?p=6358
*void findsum(node *T,int key)
{
@Piyush..
I tried your algo on BST {5,4,6,3,2,1,8,7,10,12,9,11}.
Its only returning 1+7.
Other pairs are 5+3, 6+2.
On Mon, Jul 11, 2011 at 6:56 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote:
@AanchalI think my following algo will work..its a modification of
Morris traversal...check if you
@Anchalthanks for pointing out the error...i found where the error
is...it is the else loop in this line in this checking...
if(p1-right == cur1 || p2-left == cur2)
actually before i have already assigned p1-right == cur1 (or
p2-left=cur2)..it shud have been in else loop..soryy for the
Check this one once..I hope it will work now..I hv introduced two more
variables check1 and check2
*
void findsum(node *T,int key)
{
int n = countnodes(T);//returns the number of nodes in the BST
int i=0;
int j=n-1;
node *cur1,*cur2,*p1,*p2;
cur1=cur2=T;
int
12 matches
Mail list logo
