wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Sum = x in BST
        
(Message started by: cesc_fabregas on Jul 2nd, 2009, 5:18am)
Title: Sum = x in BST
Post by cesc_fabregas on Jul 2nd, 2009, 5:18am
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?
Title: Re: Sum = x in BST
Post by SMQ on Jul 2nd, 2009, 5:40am
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
Title: Re: Sum = x in BST
Post by cesc_fabregas on Jul 2nd, 2009, 5:45am
What if we are given a binary tree instead of BST?
Title: Re: Sum = x in BST
Post by SMQ on Jul 2nd, 2009, 6:00am
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
Title: Re: Sum = x in BST
Post by towr on Jul 2nd, 2009, 6:00am

on 07/02/09 at 05:45:33, 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.
Title: Re: Sum = x in BST
Post by R on Jul 2nd, 2009, 7:42am
Do we have better than O(n lg n) for the original problem (the one with values in BST)?
Title: Re: Sum = x in BST
Post by SMQ on Jul 2nd, 2009, 7:56am

on 07/02/09 at 07:42:27, 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
Title: Re: Sum = x in BST
Post by cesc_fabregas on Jul 2nd, 2009, 7:59am
@SMQ

Even if the values are sorted, how can we achieve O(n) performance? I doubt.
Title: Re: Sum = x in BST
Post by R on Jul 2nd, 2009, 8:00am
[hide]With the two pointers on opposite ends??[/hide]
Title: Re: Sum = x in BST
Post by cesc_fabregas on Jul 2nd, 2009, 8:02am
@R

This won't work without parent pointers..........
Title: Re: Sum = x in BST
Post by SMQ on Jul 2nd, 2009, 8:07am
@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
Title: Re: Sum = x in BST
Post by ONS on Jul 8th, 2009, 7:41am
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?
Title: Re: Sum = x in BST
Post by SMQ on Jul 8th, 2009, 7:51am
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
Title: Re: Sum = x in BST
Post by srikanth.iiita on Mar 20th, 2010, 8:03am
@SMQ
can u be more clear...
iam not able to get this point ....how it is O(n)....
Title: Re: Sum = x in BST
Post by blackJack on Apr 2nd, 2010, 12:31am
@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?
Title: Re: Sum = x in BST
Post by SMQ on Apr 2nd, 2010, 4:28am

on 03/20/10 at 08:03:59, 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 04/02/10 at 00:31:42, 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
Title: Re: Sum = x in BST
Post by blackJack on Apr 2nd, 2010, 4:56am
Yes ...got it  :) thanks a lot, SMQ


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board