Re: [algogeeks] Re: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K.
OK... suppose our tree is 5 /\ 4 6 / \ 3 7 / \ 2 8 / \ 1 9 now k=10; so will it return all the pairs like 1,9 2,8 . . ..5,5. . . .. .8,2 9,1 ?? On Sun, Jul 17, 2011 at 7:00 AM, saurabh singh saurab...@gmail.com wrote: @sagar This is what Dave is suggesting in a more pseudocode way:- 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 the same but I am assuming rev inorder to be right-node-left) else set small to its inorder successor. break when u get the desired k. print :) return if u get out of the loop without getting the number then such number does not exist.print :( Amortized complexity order n. -- Saurabh Singh B.Tech (Computer Science) 5h sem MNNIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K.
9 1 is analogous to 1 9...And the question requires only two nodes,it does not says about all such pairs. On Sun, Jul 17, 2011 at 2:52 PM, sagar pareek sagarpar...@gmail.com wrote: OK... suppose our tree is 5 /\ 4 6 / \ 3 7 / \ 2 8 / \ 1 9 now k=10; so will it return all the pairs like 1,9 2,8 . . ..5,5. . . .. .8,2 9,1 ?? On Sun, Jul 17, 2011 at 7:00 AM, saurabh singh saurab...@gmail.comwrote: @sagar This is what Dave is suggesting in a more pseudocode way:- 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 the same but I am assuming rev inorder to be right-node-left) else set small to its inorder successor. break when u get the desired k. print :) return if u get out of the loop without getting the number then such number does not exist.print :( Amortized complexity order n. -- Saurabh Singh B.Tech (Computer Science) 5h sem MNNIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K.
OK On Sun, Jul 17, 2011 at 2:59 PM, saurabh singh saurab...@gmail.com wrote: 9 1 is analogous to 1 9...And the question requires only two nodes,it does not says about all such pairs. On Sun, Jul 17, 2011 at 2:52 PM, sagar pareek sagarpar...@gmail.comwrote: OK... suppose our tree is 5 /\ 4 6 / \ 3 7 / \ 2 8 / \ 1 9 now k=10; so will it return all the pairs like 1,9 2,8 . . ..5,5. . . .. .8,2 9,1 ?? On Sun, Jul 17, 2011 at 7:00 AM, saurabh singh saurab...@gmail.comwrote: @sagar This is what Dave is suggesting in a more pseudocode way:- 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 the same but I am assuming rev inorder to be right-node-left) else set small to its inorder successor. break when u get the desired k. print :) return if u get out of the loop without getting the number then such number does not exist.print :( Amortized complexity order n. -- Saurabh Singh B.Tech (Computer Science) 5h sem MNNIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K.
@dave what if the k= root-left + right most leaf ? how ur algo works on it? On Sat, Jul 16, 2011 at 9:28 PM, Dave dave_and_da...@juno.com wrote: @Noobcoder: To do it in O(n) without destroying the BST, do two inorder traversals simultaneously, one in the normal forward (left subtree first) direction and one in the reverse direction (right subtree first). Let the two current nodes have value F and R respectively. If F + R = K, return success. If F = R, return failure. If F + R K, advance the forward traversal. Otherwise (F + R K), advance the reverse traversal. To do the traversals simultaneously, you will have to use explicit stacks instead of recursion. Dave On Jul 16, 9:01 am, noobcoder ase.as...@gmail.com wrote: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K.
ok i got it actually u written wrong that f/w and reverse traversal are running parallel u must wrote that f/w traversal inside reverse or vice versa On Sat, Jul 16, 2011 at 10:35 PM, Dave dave_and_da...@juno.com wrote: @Sagar: No problem. The algorithm would do only forward traversal steps until it got to root_left, whereupon F + R = K. Dave On Jul 16, 11:40 am, sagar pareek sagarpar...@gmail.com wrote: @dave what if the k= root-left + right most leaf ? how ur algo works on it? On Sat, Jul 16, 2011 at 9:28 PM, Dave dave_and_da...@juno.com wrote: @Noobcoder: To do it in O(n) without destroying the BST, do two inorder traversals simultaneously, one in the normal forward (left subtree first) direction and one in the reverse direction (right subtree first). Let the two current nodes have value F and R respectively. If F + R = K, return success. If F = R, return failure. If F + R K, advance the forward traversal. Otherwise (F + R K), advance the reverse traversal. To do the traversals simultaneously, you will have to use explicit stacks instead of recursion. Dave On Jul 16, 9:01 am, noobcoder ase.as...@gmail.com wrote: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K.
and so it must not be O(n) On Sat, Jul 16, 2011 at 10:54 PM, sagar pareek sagarpar...@gmail.comwrote: ok i got it actually u written wrong that f/w and reverse traversal are running parallel u must wrote that f/w traversal inside reverse or vice versa On Sat, Jul 16, 2011 at 10:35 PM, Dave dave_and_da...@juno.com wrote: @Sagar: No problem. The algorithm would do only forward traversal steps until it got to root_left, whereupon F + R = K. Dave On Jul 16, 11:40 am, sagar pareek sagarpar...@gmail.com wrote: @dave what if the k= root-left + right most leaf ? how ur algo works on it? On Sat, Jul 16, 2011 at 9:28 PM, Dave dave_and_da...@juno.com wrote: @Noobcoder: To do it in O(n) without destroying the BST, do two inorder traversals simultaneously, one in the normal forward (left subtree first) direction and one in the reverse direction (right subtree first). Let the two current nodes have value F and R respectively. If F + R = K, return success. If F = R, return failure. If F + R K, advance the forward traversal. Otherwise (F + R K), advance the reverse traversal. To do the traversals simultaneously, you will have to use explicit stacks instead of recursion. Dave On Jul 16, 9:01 am, noobcoder ase.as...@gmail.com wrote: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K.
Ok may be i m not getting ur logic... On Sat, Jul 16, 2011 at 11:03 PM, Dave dave_and_da...@juno.com wrote: @Sagar: No. I didn't say that they were in parallel or that one was inside the other. Go back and read it again and you will see that I said that they were being performed simultaneously, with each one being advanced in certain circumstances, and that in order to do that you would have to use explicit stacks instead of recursion. Perhaps, instead, you misread or misunderstood it. Dave On Jul 16, 12:24 pm, sagar pareek sagarpar...@gmail.com wrote: ok i got it actually u written wrong that f/w and reverse traversal are running parallel u must wrote that f/w traversal inside reverse or vice versa On Sat, Jul 16, 2011 at 10:35 PM, Dave dave_and_da...@juno.com wrote: @Sagar: No problem. The algorithm would do only forward traversal steps until it got to root_left, whereupon F + R = K. Dave On Jul 16, 11:40 am, sagar pareek sagarpar...@gmail.com wrote: @dave what if the k= root-left + right most leaf ? how ur algo works on it? On Sat, Jul 16, 2011 at 9:28 PM, Dave dave_and_da...@juno.com wrote: @Noobcoder: To do it in O(n) without destroying the BST, do two inorder traversals simultaneously, one in the normal forward (left subtree first) direction and one in the reverse direction (right subtree first). Let the two current nodes have value F and R respectively. If F + R = K, return success. If F = R, return failure. If F + R K, advance the forward traversal. Otherwise (F + R K), advance the reverse traversal. To do the traversals simultaneously, you will have to use explicit stacks instead of recursion. Dave On Jul 16, 9:01 am, noobcoder ase.as...@gmail.com wrote: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K.
You must take an example and then explain On Sat, Jul 16, 2011 at 11:59 PM, Dave dave_and_da...@juno.com wrote: @Sagar: If you are not getting my logic, ask a question. Dave On Jul 16, 12:35 pm, sagar pareek sagarpar...@gmail.com wrote: Ok may be i m not getting ur logic... On Sat, Jul 16, 2011 at 11:03 PM, Dave dave_and_da...@juno.com wrote: @Sagar: No. I didn't say that they were in parallel or that one was inside the other. Go back and read it again and you will see that I said that they were being performed simultaneously, with each one being advanced in certain circumstances, and that in order to do that you would have to use explicit stacks instead of recursion. Perhaps, instead, you misread or misunderstood it. Dave On Jul 16, 12:24 pm, sagar pareek sagarpar...@gmail.com wrote: ok i got it actually u written wrong that f/w and reverse traversal are running parallel u must wrote that f/w traversal inside reverse or vice versa On Sat, Jul 16, 2011 at 10:35 PM, Dave dave_and_da...@juno.com wrote: @Sagar: No problem. The algorithm would do only forward traversal steps until it got to root_left, whereupon F + R = K. Dave On Jul 16, 11:40 am, sagar pareek sagarpar...@gmail.com wrote: @dave what if the k= root-left + right most leaf ? how ur algo works on it? On Sat, Jul 16, 2011 at 9:28 PM, Dave dave_and_da...@juno.com wrote: @Noobcoder: To do it in O(n) without destroying the BST, do two inorder traversals simultaneously, one in the normal forward (left subtree first) direction and one in the reverse direction (right subtree first). Let the two current nodes have value F and R respectively. If F + R = K, return success. If F = R, return failure. If F + R K, advance the forward traversal. Otherwise (F + R K), advance the reverse traversal. To do the traversals simultaneously, you will have to use explicit stacks instead of recursion. Dave On Jul 16, 9:01 am, noobcoder ase.as...@gmail.com wrote: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K.
Use O(2n) memory , list the in-order traversal of BST say A[0..n]. and K-A[0...n] say B . Now apply standard merge function(Merge sort) on A and B. keeping track of equal found elements during comparison to get the ans. On 7/17/11, sagar pareek sagarpar...@gmail.com wrote: You must take an example and then explain On Sat, Jul 16, 2011 at 11:59 PM, Dave dave_and_da...@juno.com wrote: @Sagar: If you are not getting my logic, ask a question. Dave On Jul 16, 12:35 pm, sagar pareek sagarpar...@gmail.com wrote: Ok may be i m not getting ur logic... On Sat, Jul 16, 2011 at 11:03 PM, Dave dave_and_da...@juno.com wrote: @Sagar: No. I didn't say that they were in parallel or that one was inside the other. Go back and read it again and you will see that I said that they were being performed simultaneously, with each one being advanced in certain circumstances, and that in order to do that you would have to use explicit stacks instead of recursion. Perhaps, instead, you misread or misunderstood it. Dave On Jul 16, 12:24 pm, sagar pareek sagarpar...@gmail.com wrote: ok i got it actually u written wrong that f/w and reverse traversal are running parallel u must wrote that f/w traversal inside reverse or vice versa On Sat, Jul 16, 2011 at 10:35 PM, Dave dave_and_da...@juno.com wrote: @Sagar: No problem. The algorithm would do only forward traversal steps until it got to root_left, whereupon F + R = K. Dave On Jul 16, 11:40 am, sagar pareek sagarpar...@gmail.com wrote: @dave what if the k= root-left + right most leaf ? how ur algo works on it? On Sat, Jul 16, 2011 at 9:28 PM, Dave dave_and_da...@juno.com wrote: @Noobcoder: To do it in O(n) without destroying the BST, do two inorder traversals simultaneously, one in the normal forward (left subtree first) direction and one in the reverse direction (right subtree first). Let the two current nodes have value F and R respectively. If F + R = K, return success. If F = R, return failure. If F + R K, advance the forward traversal. Otherwise (F + R K), advance the reverse traversal. To do the traversals simultaneously, you will have to use explicit stacks instead of recursion. Dave On Jul 16, 9:01 am, noobcoder ase.as...@gmail.com wrote: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K. -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD- Hide quoted text - - Show quoted text - -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group.
Re: [algogeeks] Re: Given a BST containing integers, and a value K. You have to find two nodes that give sum = K.
@sagar This is what Dave is suggesting in a more pseudocode way:- 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 the same but I am assuming rev inorder to be right-node-left) else set small to its inorder successor. break when u get the desired k. print :) return if u get out of the loop without getting the number then such number does not exist.print :( Amortized complexity order n. -- Saurabh Singh B.Tech (Computer Science) 5h sem MNNIT ALLAHABAD -- 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
