Author |
Topic: Sum = x in BST (Read 2527 times) |
|
cesc_fabregas
Newbie
Posts: 14
|
 |
Sum = x in BST
« on: Jul 2nd, 2009, 5:18am » |
 Quote  Modify
|
Given a BST containing integers and a value K. You have to find two nodes that give sum = K.
What could be the best solution to this?
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 2084
|
|
Re: Sum = x in BST
« Reply #1 on: Jul 2nd, 2009, 5:40am » |
Quote Modify
|
Can you see an efficient way to solve the problem given a sorted array rather than a BST? The same strategy will work for a BST.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
cesc_fabregas
Newbie
Posts: 14
|
|
Re: Sum = x in BST
« Reply #2 on: Jul 2nd, 2009, 5:45am » |
Quote Modify
|
What if we are given a binary tree instead of BST?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Sum = x in BST
« Reply #3 on: Jul 2nd, 2009, 6:00am » |
Quote Modify
|
Then I don't think you can do better than to sort it first (into an array or a BST, take your pick) and use the algorithm for a sorted sequence.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sum = x in BST
« Reply #4 on: Jul 2nd, 2009, 6:00am » |
Quote Modify
|
on Jul 2nd, 2009, 5:45am, cesc_fabregas wrote:| What if we are given a binary tree instead of BST? |
|
Then it's a lot more work. You could use a hash-map, or sort the tree.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Sum = x in BST
« Reply #5 on: Jul 2nd, 2009, 7:42am » |
Quote Modify
|
Do we have better than O(n lg n) for the original problem (the one with values in BST)?
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Sum = x in BST
« Reply #6 on: Jul 2nd, 2009, 7:56am » |
Quote Modify
|
on Jul 2nd, 2009, 7:42am, R wrote:| Do we have better than O(n lg n) for the original problem (the one with values in BST)? |
|
Yes, there is a straightforward O(n) algorithm for the case where the values are sorted.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
cesc_fabregas
Newbie
Posts: 14
|
|
Re: Sum = x in BST
« Reply #7 on: Jul 2nd, 2009, 7:59am » |
Quote Modify
|
@SMQ
Even if the values are sorted, how can we achieve O(n) performance? I doubt.
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Sum = x in BST
« Reply #8 on: Jul 2nd, 2009, 8:00am » |
Quote Modify
|
With the two pointers on opposite ends??
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
cesc_fabregas
Newbie
Posts: 14
|
|
Re: Sum = x in BST
« Reply #9 on: Jul 2nd, 2009, 8:02am » |
Quote Modify
|
@R
This won't work without parent pointers..........
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Sum = x in BST
« Reply #10 on: Jul 2nd, 2009, 8:07am » |
Quote Modify
|
@R: yep; @cesc_fabregas: sure it will, you just need to keep careful track of your traversal (using O(log n) memory, either with explicit stacks or with recursion).
ETA: code
#include <stack>
#include <utility>
using namespace std;
typedef struct Node { int value; Node *left, *right; } *NodePtr;
typedef pair<NodePtr, NodePtr> NodePair;
NodePair findAddends(NodePtr tree, int sum) {
// "iterators" for tree traversal
stack<NodePtr> fwdIt, revIt;
fwdIt.push(tree); while (fwdIt.top()->left) fwdIt.push(fwdIt.top()->left);
revIt.push(tree); while (revIt.top()->right) revIt.push(revIt.top()->right);
while (fwdIt.top() != revIt.top()) {
// check for match
if (fwdIt.top()->value + revIt.top()->value == sum) {
return NodePair(fwdIt.top(), revIt.top());
}
// move appropriate iterator
NodePtr p;
if (fwdIt.top()->value + revIt.top()->value < sum) {
// increment forward iterator
if (fwdIt.top()->right) {
fwdIt.push(fwdIt.top()->right);
while (fwdIt.top()->left) fwdIt.push(fwdIt.top()->left);
} else {
do {
p = fwdIt.top();
fwdIt.pop();
} while (!fwdIt.empty() && p == fwdIt.top()->right);
}
} else {
// decrement reverse iterator
if (revIt.top()->left) {
revIt.push(revIt.top()->left);
while (revIt.top()->right) revIt.push(revIt.top()->right);
} else {
do {
p = revIt.top();
revIt.pop();
} while (!revIt.empty() && p == revIt.top()->left);
}
}
}
// no match found
return NodePair(NULL, NULL);
}
--SMQ
|
| « Last Edit: Jul 2nd, 2009, 10:46am by SMQ » |
IP Logged |
--SMQ
|
|
|
ONS
Newbie
Gender:
Posts: 41
|
|
Re: Sum = x in BST
« Reply #11 on: Jul 8th, 2009, 7:41am » |
Quote Modify
|
in a sorted array we can use two pointers on both end and traversing involvees only incrementing or decrementing the pointer, so O(n).
but in bst, we need to find the successor or predecessor, which may require O(lgn) storage space along with O(lgn) iteration to reach the parent which is a succ. or pred.
so howz it going to be O(n). am i missing something?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Sum = x in BST
« Reply #12 on: Jul 8th, 2009, 7:51am » |
Quote Modify
|
In the traversal, each node is "encountered" at most three times: once when traversing downward into the left (right) child tree, once when visiting the node itself, and once when traversing upward from the right (left) child tree. Thus the overall traversal is at worst O(log n) memory (O(1) if the tree has parent pointers) and O(n) time.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
srikanth.iiita
Newbie
Posts: 33
|
|
Re: Sum = x in BST
« Reply #13 on: Mar 20th, 2010, 8:03am » |
Quote Modify
|
@SMQ
can u be more clear...
iam not able to get this point ....how it is O(n)....
|
|
IP Logged |
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Sum = x in BST
« Reply #14 on: Apr 2nd, 2010, 12:31am » |
Quote Modify
|
@SMQ,
Code:
do {
p = fwdIt.top();
fwdIt.pop();
} while (!fwdIt.empty() && p == fwdIt.top()->right);
|
|
In forward traversal, what is the need of a do-while loop, when top() has no right child, should it just not pop out the current top? I think it is done to remove identical values from tree to make the code efficient. Am I right?
|
|
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Sum = x in BST
« Reply #15 on: Apr 2nd, 2010, 4:28am » |
Quote Modify
|
on Mar 20th, 2010, 8:03am, srikanth.iiita wrote:@SMQ
can u be more clear...
iam not able to get this point ....how it is O(n).... |
|
The number of times a node is visited by the traversal does not depend in any way on the number of other nodes in the tree, rather, it is at most three in all cases. Therefore the traversal visits at most 3n nodes redargless of n. 3n is, by definition, O(n). Hope that's clearer.
on Apr 2nd, 2010, 12:31am, blackJack wrote:@SMQ,
Code:
do {
p = fwdIt.top();
fwdIt.pop();
} while (!fwdIt.empty() && p == fwdIt.top()->right);
|
|
In forward traversal, what is the need of a do-while loop, when top() has no right child, should it just not pop out the current top? I think it is done to remove identical values from tree to make the code efficient. Am I right? |
|
No. the forward traversal is:
Traverse left as far as possible
Loop
Visit Node
If possible,
Traverse right
Traverse left as far as possible
Else
Traverse up
While the traverse up was from the right child
Traverse Up
The loop you point out is in yellow. Without it, the next pass of the outer loop would revisit the right child we just left, causing an infinite loop. It's the "reverse" if you will of the "Traverse left as far as possible" step--i.e. we could rewrite the algorithm as:
Traverse down and left as far as possible
Loop
Visit Node
If possible,
Traverse down and right
Traverse down and left as far as possible
Else
Traverse up and left as far as pssible
Traverse up and right
Clear?
--SMQ
|
| « Last Edit: Apr 2nd, 2010, 4:57am by SMQ » |
IP Logged |
--SMQ
|
|
|
blackJack
Junior Member
2b \/ ~2b
Gender:
Posts: 55
|
|
Re: Sum = x in BST
« Reply #16 on: Apr 2nd, 2010, 4:56am » |
Quote Modify
|
Yes ...got it  thanks a lot, SMQ
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print