StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><strong>To preserve the tree and only use O(1) space it's possible if...</strong></p> <ul> <li>Each node is a fixed size.</li> <li>The whole tree is in a contiguous part of memory (i.e. an array)</li> <li>You don't iterate over the tree, you simply iterate over the array</li> </ul> <p><strong>Or if you destroy the tree as you process it...:</strong></p> <ul> <li>@Svante came up with this idea, but I wanted to expand on <strong>how</strong> a little, using a destructive approach. </li> <li>How? You can continue to take the left most <strong>leaf</strong> node in a tree (for(;;) node = node->left etc... , then process it, then delete it. If the leftmost node in the tree is not a leaf node, then you process and delete the right node's left most leaf node. If a right node has no children, then you process and delete it. </li> </ul> <p><strong>Ways that it wouldn't work...</strong></p> <p>If you use recursion you will use a stack implicitly. For some algorithms (not for this problem) tail recursion would allow you to use recursion and have O(1) space, but since any particular node may have several children, and hence there is work to do after the recursive call, O(1) space tail recursion is not possible. </p> <p>You could try to tackle the problem 1 level at a time, but there is no way to access an arbitrary level's nodes without auxiliary (implicit or explicit) space. For example you could recurse to find the node you want, but then that takes implicit stack space. Or you could store all your nodes in another data structure per level, but that takes extra space too.</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