CODEWITHSUNDEEP
data-structurestreetime-complexity
Rotem
Rotem

Reputation: 13

LCA in binary tree O(n) space O(1) time

I need to find data structure that uses pre-processing on a binary tree and answers the LCA query in O(n) space and O(1) time.

Which data structure helps in this case? Thank you

Upvotes: 0

Views: 505

Answers (1)

templatetypedef
templatetypedef

Reputation: 372764

There are a couple of data structures that solve this problem. The most common approach is to use a data structure for the range minimum query problem, which can be solved with O(n) preprocessing time and O(1) query time, and then using that to solve LCA. I put together a two-part series of lecture slides on this topic for a class I taught earlier this year.

  • Part one talks about the range minimum query problem and motivates a couple common solution strategies.
  • Part two talks about the Fischer-Heun RMQ structure, which meets the requisite time bounds, and how to use it to solve LCA.

For what it's worth, in practice, there are solutions that use O(n) preprocessing time and O(log n) query time but are faster than the equivalent worst-case efficient structures. The ⟨O(n), O(log n)⟩ hybrid described in the first set of lecture slides is, for most practical purposes, good enough.

Upvotes: 1

Related Questions