StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Although you are right that finding an in-order successor or predecessor might take O(h) time, it turns out that if you start at the smallest value in a BST and repeatedly find its successor, the total amount of work done ends up coming out to O(n) regardless of the shape of the tree.</p> <p>On intuition for this is to think about how many times you traverse each edge in the tree when iteratively doing successor lookups. Specifically, you will visit every edge in the tree exactly twice: once when you descend into the subtree, and once when you walk up out of it having visited every node in that subtree. Since an n-node tree has O(n) edges, this takes time O(n) to complete.</p> <p>If you're skeptical about this, try writing a simple program to verify it. I remember not believing this result when I first heard it until I wrote a program to confirm it. :-)</p> <p>In pseudocode, the logic would look like this:</p> <ol> <li>Find the lowest value in the tree by starting at the root and repeatedly following the left child pointer until no such pointer exists.</li> <li>Until all nodes are visited, remember the current node and find its successor as follows: <ol> <li>If the current node has a right child: <ol> <li>Go right.</li> <li>Go left until there are no left children left.</li> <li>Output the node you started at, then this node. 2: Otherwise:</li> <li>Walk up to the parent node until you find that the node you started at was a left child of its parent.</li> <li>If you hit the root and never found that you traversed from a left child upward, you are done.</li> <li>Otherwise, output the node you remembers, then the current node.</li> </ol></li> </ol></li> </ol> <p>Hope this helps!</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