StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Nick Johnson is correct that a an O(n) time complexity algorithm is the best you can do if you have no parent pointers.) For a simple recursive version of that algorithm see the code in <a href="https://stackoverflow.com/a/5000698/179917">Kinding's post</a> which runs in O(n) time.</p> <p>But keep in mind that if your nodes have parent pointers, an improved algorithm is possible. For both nodes in question construct a list containing the path from root to the node by starting at the node, and front inserting the parent.</p> <p>So for 8 in your example, you get (showing steps): {4}, {2, 4}, {1, 2, 4}</p> <p>Do the same for your other node in question, resulting in (steps not shown): {1, 2}</p> <p>Now compare the two lists you made looking for the first element where the list differ, or the last element of one of the lists, whichever comes first.</p> <p>This algorithm requires O(h) time where h is the height of the tree. In the worst case O(h) is equivalent to O(n), but if the tree is balanced, that is only O(log(n)). It also requires O(h) space. An improved version is possible that uses only constant space, with code shown in <a href="https://stackoverflow.com/a/6183069/179917">CEGRD's post</a></p> <hr> <p>Regardless of how the tree is constructed, if this will be an operation you perform many times on the tree without changing it in between, there are other algorithms you can use that require O(n) [linear] time preparation, but then finding any pair takes only O(1) [constant] time. For references to these algorithms, see the the lowest common ancestor problem page on <a href="http://en.wikipedia.org/wiki/Lowest_common_ancestor" rel="noreferrer">Wikipedia</a>. (Credit to Jason for originally posting this link)</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