StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p><a href="http://en.wikipedia.org/wiki/Recursion" rel="nofollow">http://en.wikipedia.org/wiki/Recursion</a></p> <p>For recursion to work you need a base case, and a set of cases and actions that reduce towards the base case.</p> <p>For counting the number of nodes in a binary trees, we can use the base case of "a node does not exists", and other case of "a node does exist".</p> <p>For the other case, (node does exist) we will add 1 to the count of nodes add the number of nodes in each of the tree's subtrees (left and right) to the total count. How do we find the number of nodes in the subtrees? Simply apply the same set of conditions that we used for the first node to the child nodes.</p> <p>By repeatedly breaking down the tree's subnodes we can obtain the total number of nodes in the tree</p> <p>Take for example:</p> <pre><code> N1 /\ N2 N3 /\ \ N4 N5 N6 </code></pre> <p>Let's call our counting method countNodes(). </p> <p>pseudocode for countNodes</p> <pre><code>int countNodes(Node parent): if parent: return 1 + countNodes(parent.left) + countNodes(parent.right) else: return 0 </code></pre> <p>countNodes will first check if the node you pass to it exists.</p> <p>If not (base case) return 0 [logically this makes sense because if the node doesnt exist, there will be no nodes in it's subtree's that dont exist]</p> <p>If the node exists you will return 1 + the sum of the number of nodes in the subtrees. To find the number of nodes in the subtrees we will just call our countNodes() method on each child node.</p> <p>In the example tree above we start with N1. We see that N1 exists so what we need to find now is: </p> <p><code>1 + # of nodes in the left subtree + # of nodes in the right subtree.</code> </p> <p>N1's subtrees are:</p> <pre><code> Left Right N2 N3 /\ \ N4 N5 N6 </code></pre> <p>We start by calling the countNodes() method on N2 (N1's left subtree). </p> <p>N2 exists so now we are looking for </p> <p><code>1 + # of nodes in N2's left subtree + # of nodes in N2's right subtree</code></p> <p>N2's subtrees are:</p> <pre><code>Left Right N4 N5 </code></pre> <p>calling countNodes() on N4 we are looking for</p> <p><code>1 + # of nodes in N4's left subtree + # of nodes in N4's right subtree</code></p> <p>N4's left node is null so when countNodes() is called on N4's left node it will return 0 (base case).</p> <p>N4's right node is also null so countNodes() for the right node is also going to return 0</p> <p>N4's pending operations can complete and you have 1 + 0 + 0 (non-base case return value)</p> <p>Now N2's pending operation looks like</p> <p><code>1 + 1 + # of nodes right subtree</code></p> <p>calling countNodes() on N5 results in the same value as N4 so N2's return value has become:</p> <p><code>1 + 1 + 1</code></p> <p>N2 returns 3 to N1's pending operation to make it look like:</p> <p><code>1 + 3 + # nodes in right subtree</code></p> <pre><code># nodes in N3 subtree is: countNodes() on N3 returns 1 + countNodes->null (base) + countNodes()->N6 # nodes in N6 subtree is countNodes() on N6 returns 1 + countNodes->null (base) + countNodes()->null (base) return value = 1 # nodes in N3 subtree is 1 + 0 + 1 returns 2 finally the call on N1's countNodes() can complete with 1 + 3 + 2 countNodes() on N1 returns 6 </code></pre> <p>To count all the right nodes in a tree you can use the following pseudocode:</p> <pre><code>int countRightNodes(Node parent): if !parent: return 0 if has right node: return 1 + (# of right nodes in left subtree) + (# of right nodes in right subtree) else: return (# of right nodes in left subtree) </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