StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>My answer is <code>O(n^2)</code>, but I believe it is accurate, and takes a <em>slightly</em> different approach and looks easier to implement.</p> <p>Assume the value stored at node <code>i</code> is denoted by <code>VALUE[i]</code>. My idea is to store at each node the sum of the values on the path from <code>root</code> to that node. So for each node <code>i</code>, <code>SUM[i]</code> is sum of path from <code>root</code> to node <code>i</code>. </p> <p>Then for each node pair <code>(i,j)</code>, find their common ancestor <code>k</code>. If <code>SUM(i)+SUM(j)-SUM(k) = TARGET_SUM</code>, you have found an answer. </p> <p>This is <code>O(n^2)</code> since we are looping over all node pairs. Although, I wish I can figure out a better way than just picking all pairs.</p> <p>We could optimize it a little by discarding subtrees where the <code>value</code> of the node rooted at the subtree is greater than <code>TARGET_SUM</code>. Any further optimizations are welcome :)</p> <p>Psuedocode:</p> <pre><code># Skipping code for storing sum of values from root to each node i in SUM[i] for i in nodes: for j in nodes: k = common_ancestor(i,j) if ( SUM[i] + SUM[j] - SUM[k] == TARGET_SUM ): print_path(i,k,j) </code></pre> <p>Function <code>common_ancestor</code> is a pretty standard problem for a binary search tree. Psuedocode (from memory, hopefully there are no errors!):</p> <pre><code>sub common_ancestor (i, j): parent_i = parent(i) # Go up the parent chain until parent's value is out of the range. # That's a red flag. while( VAL[i] <= VAL[parent_i] <= VAL[j] ) : last_parent = parent_i parent_i = parent(i) if ( parent_i == NULL ): # root node break return last_parent </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload