StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Cool puzzle! I hopes its not an assignment, cuz I'm about to spoil it.</p> <p>`pre_order(u.right) - pre_order(u.left) + post_order(u.right) - post_order(u.left) + 1 == number of nodes in the subtree.</p> <p><code>pre_order(u.right) - pre_order(u.left)</code> computes the number of nodes in the left child because the "distance" from the beginning of the left child to the beginning of the right child is the size of the left child.</p> <p>Similarly, <code>post_order(u.right) - post_order(u.left)</code> computes the number of nodes in the right child because the difference between end of the left and end of the right child is the size of the right child.</p> <p>Adding 1 includes the root of the tree itself. Obviously either term could be zero if there are no children on that side.</p> <hr> <p>The nodes in the trees shown above do no have names. My understanding is that the numbers in the pictures above represent the value of <code>pre_order(x)</code> or <code>post_order(x)</code> or <code>in_order(x)</code>, where <code>x</code> is a node whose name we do not know, but whose position in the tree is obvious to viewers. </p> <p>In "real life" each node would include: (optional name), in_order value, pre_order value, post_order value, (optional) left child, (optional) right child, and optionally other information. </p> <p>Consider the bottom-right-most node; <code>post_order(u)==8</code>, <code>post_order(u.left)</code> is undefined, as is <code>pre_order(u.left)</code>, and <code>in_order(u.right)</code> and so on, since it has no children.</p> <p>Consider the node <code>u</code> such that <code>pre_order(u)==post_order(u)==in_order(u)==3</code>, then <code>post_order(u.left)==1</code> and <code>pre_order(u.right)==5</code>.</p>

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