StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
13109199
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
12
CommunityOwnedDate
CreationDate
2012-10-28T13:32:49.463
FavoriteCount
0
LastActivityDate
2012-10-28T17:56:18.393
LastEditDate
2012-10-28T17:56:18.393
LastEditorUserId
47984
OwnerUserId
47984
ParentId
13104692
PostTypeId
2
Score
2
ViewCount
0
LastEditorDisplayName
text
Body
You can certainly generate all possible paths, summing incrementally as you go. The fact that the tree is a BST might let you save time by bounding out certain sums, though I'm not sure that will give an asymptotic speed increase. The problem is that a sum formed using the left child of a given node will not necessarily be less than a sum formed using the right child, since the path for the former sum could contain many more nodes. The following algorithm will work for all trees, not just BSTs. To generate all possible paths, notice that the topmost point of a path is special: it's the only point in a path which is allowed (though not required) to have both children contained in the path. Every path contains a unique topmost point. Therefore the outer layer of recursion should be to visit every tree node, and to generate all paths that have that node as the topmost point. <pre><code>// Report whether any path whose topmost node is t sums to target. // Recurses to examine every node under t. EnumerateTopmost(Tree t, int target) { // Get a list of sums for paths containing the left child. // Include a 0 at the start to account for a "zero-length path" that // does not contain any children. This will be in increasing order. a = append(0, EnumerateSums(t.left)) // Do the same for paths containing the right child. This needs to // be sorted in decreasing order. b = reverse(append(0, EnumerateSums(t.right))) // "List match" to detect any pair of sums that works. // This is a linear-time algorithm that takes two sorted lists -- // one increasing, the other decreasing -- and detects whether there is // any pair of elements (one from the first list, the other from the // second) that sum to a given value. Starting at the beginning of // each list, we compute the current sum, and proceed to strike out any // elements that we know cannot be part of a satisfying pair. // If the sum of a[i] and b[j] is too small, then we know that a[i] // cannot be part of any satisfying pair, since all remaining elements // from b that it could be added to are at least as small as b[j], so we // can strike it out (which we do by advancing i by 1). Similarly if // the sum of a[i] and b[j] is too big, then we know that b[j] cannot // be part of any satisfying pair, since all remaining elements from a // that b[j] could be added to are at least as big as a[i], so we can // strike it out (which we do by advancing j by 1). If we get to the // end of either list without finding the right sum, there can be // no satisfying pair. i = 0 j = 0 while (i < length(a) and j < length(b)) { if (a[i] + b[j] + t.value < target) { i = i + 1 } else if (a[i] + b[j] + t.value > target) { j = j + 1 } else { print "Found! Topmost node=", t return } } // Recurse to examine the rest of the tree. EnumerateTopmost(t.left) EnumerateTopmost(t.right) } // Return a list of all sums that contain t and at most one of its children, // in increasing order. EnumerateSums(Tree t) { If (t == NULL) { // We have been called with the "child" of a leaf node. return [] // Empty list } else { // Include a 0 in one of the child sum lists to stand for // "just node t" (arbitrarily picking left here). // Note that even if t is a leaf node, we still call ourselves on // its "children" here -- in C/C++, a special "NULL" value represents // these nonexistent children. a = append(0, EnumerateSums(t.left)) b = EnumerateSums(t.right) Add t.value to each element in a Add t.value to each element in b // "Ordinary" list merge that simply combines two sorted lists // to produce a new sorted list, in linear time. c = ListMerge(a, b) return c } } </code></pre> The above pseudocode only reports the topmost node in the path. The entire path can be reconstructed by having <code>EnumerateSums()</code> return a list of pairs <code>(sum, goesLeft)</code> instead of a plain list of sums, where <code>goesLeft</code> is a boolean that indicates whether the path used to generate that sum initially goes left from the parent node. The above pseudocode calculates sum lists multiple times for each node: <code>EnumerateSums(t)</code> will be called once for each node above <code>t</code> in the tree, in addition to being called for <code>t</code> itself. It would be possible to make <code>EnumerateSums()</code> memoise the list of sums for each node so that it's not recomputed on subsequent calls, <s>but actually this doesn't improve the asymptotics: only O(n) work is required to produce a list of n sums using the plain recursion, and changing this to O(1) doesn't change the overall time complexity because the entire list of sums produced by any call to <code>EnumerateSums()</code> must in general be read by the caller anyway, and this requires O(n) time.</s> EDIT: As pointed out by Evgeny Kluev, <code>EnumerateSums()</code> actually behaves like a merge sort, being O(nlog n) when the tree is perfectly balanced and O(n^2) when it is a single path. So memoisation will in fact give an asymptotic performance improvement. It is possible to get rid of the temporary lists of sums by rearranging <code>EnumerateSums()</code> into an iterator-like object that performs the list merge lazily, and can be queried to retrieve the next sum in increasing order. This would entail also creating an <code>EnumerateSumsDown()</code> that does the same thing but retrieves sums in decreasing order, and using this in place of <code>reverse(append(0, EnumerateSums(t.right)))</code>. Doing this brings the space complexity of the algorithm down to O(n), where n is the number of nodes in the tree, since each iterator object requires constant space (pointers to left and right child iterator objects, plus a place to record the last sum) and there can be at most one per tree node.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POFind whether given sum exists over a path in a BST
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USj_random_hacker
UserOwnerUserId
1. USj_random_hacker
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POFind whether given sum exists over a path in a BST
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTAcceptedByOriginator
CommentsPostId

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.