StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>To get the inorder successor of a given node <code>N</code> we use the following rules:</p> <ul> <li>If <code>N</code> has a right child <code>R</code> then the <code>inorderSuccessor(N)</code> is the leftmost decedent of <code>R</code>.</li> <li>Else <code>inorderSuccessor(N)</code> is the closest ancestor, <code>M</code>, of <code>N</code> (if it exists) such that <code>N</code> is descended from the left child of <code>M</code>. If there is no such ancestor, inorderSucessor does not exist.</li> </ul> <p>Consider a sample tree:</p> <pre><code> A / \ B C / \ D E / F </code></pre> <p>Whose inorder traversal gives: <code>D B F E A C</code></p> <p><code>inorderSuccessor(A)</code> = <code>C</code> as <code>C</code> is the leftmost decedent of the right child of <code>A</code>.</p> <p><code>inorderSuccessor(B)</code> = <code>F</code> as <code>F</code> is the leftmost decedent of the right child of <code>B</code>.</p> <p><code>inorderSuccessor(C)</code> = Does not exist.</p> <p><code>inorderSuccessor(D)</code> = <code>B</code> as <code>B</code> is the left child of <code>D</code>.</p> <p><code>inorderSuccessor(E)</code> = <code>A</code>. <code>E</code> does not have a right child so we have scenario 2. We go to parent of <code>E</code> which is <code>B</code>, but <code>E</code> is right decedent of <code>B</code>, so we move to parent of <code>B</code> which is <code>A</code> and <code>B</code> is left decedent of <code>A</code> so <code>A</code> is the answer.</p> <p><code>inorderSuccessor(F)</code> = <code>E</code> as <code>F</code> is the left child of <code>E</code>.</p> <p>Procedure:</p> <pre><code>treeNodePtr inorderSucessor(treeNodePtr N) { if(N) { treeNodePtr tmp; // CASE 1: right child of N exists. if(N->right) { tmp = N->right; // find leftmost node. while(tmp->left) { tmp = tmp->left; } // CASE 2: No right child. } else { // keep climbing till you find a parent such that // node is the left decedent of it. while((tmp = N->parent)) { if(tmp->left == N) { break; } N = tmp; } } return tmp; } // No IOS. return NULL; } </code></pre> <p><a href="http://www.ideone.com/imqy2"><strong>Code In Action</strong></a></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