e-maxx's blog

By e-maxx, 12 years ago, translation, In English

Some days ago I was asked about the problem of finding least common ancestor of two given vertices. Specifically, the task is not to use any preprocessing of the tree, and a single LCA query should be answered in time O(r), where r is the distance between query vertices.

If there are no restrictions on memory usage, then the solution can be seen almost instantly: let's lift up both vertices simultaneously, and mark in two arrays all vertices visited during the first path and during the second path. As soon as we meet a vertex that is visited by both paths — this vertex will be the LCA.

But this solution requires O(n) memory, or, if we use hash-set, O(r) memory.

I started to think, is it possible to solve this problem almost without additional memory, i.e., use O(1) of memory. (Of course, the time complexity should remain the same O(r).)

And it turned out that yes, that's possible. Now I set this nice problem to you. (Possibly this is a known problem? I've never seen it before, though.)

As usual, post your solutions at comments, but hide them under edits, so that one can't read your solution accidentally.

Tags lca
  • Vote: I like it
  • +58
  • Vote: I do not like it

»
12 years ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

Solution in edit.

  • »
    »
    12 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    How to find a vertex with a bigger depth?

    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We lift up each vertex until we reach the root and we count how many vertices we passed.

      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Consider an extreme situation: the tree is a chain with root 1. When asking LCA for vetrex n and vetrex n (certainly their LCA is N...they are the same vetrex), lifting up each vetrex leads to O(n) time complexity because you have to go over the whole chain.

»
12 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

in edit