StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>A trivial recursive solution:</p> <pre><code>int count() { Tree l = getLeftTree(); Tree r = getRightTree(); return 1 + (l != null ? l.count() : 0) + (r != null ? r.count() : 0); } </code></pre> <p>A less trivial non-recursive one:</p> <pre><code>int count() { Stack<Tree> s = new Stack<Tree>(); s.push(this); int cnt = 0; while (!s.empty()) { Tree t = s.pop(); cnt++; Tree ch = getLeftTree(); if (ch != null) s.push(ch); ch = getRightTree(); if (ch != null) s.push(ch); } return cnt; } </code></pre> <p>The latter is probably slightly more memory-efficient, because it replaces recursion with a stack and an iteration. It's also probably faster, but its hard to tell without measurements. A key difference is that the recursive solution uses the stack, while the non-recursive solution uses the heap to store the nodes.</p> <p><strong>Edit:</strong> Here's a variant of the iterative solution, which uses the stack less heavily:</p> <pre><code>int count() { Tree t = this; Stack<Tree> s = new Stack<Tree>(); int cnt = 0; do { cnt++; Tree l = t.getLeftTree(); Tree r = t.getRightTree(); if (l != null) { t = l; if (r != null) s.push(r); } else if (r != null) { t = r; } else { t = s.empty() ? null : s.pop(); } } while (t != null); return cnt; } </code></pre> <p>Whether you need a more efficient or a more elegant solution naturally depends on the size of your trees and on how often you intend to use this routine. Rembemer what Hoare said: "premature optimization is the root of all evil."</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