Flawless's blog

Lowest Common Ancestor in Binary Tree (Not Binary Search Tree)
By Flawless, 12 years ago, In English

What is the most efficient way to find Lowest Common Ancestor in Binary Tree ?

  • Vote: I like it
  • +2
  • Vote: I do not like it

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

See at TopCoder Algorithm Tutorials, there is a nice explanation for Lowest Common Ancestor. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

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

You can use sparse table or RMQ , i think.

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

    i was trying to implement recursively.. but i think using RMQ would be best method

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if you don't need online LCA algorithm, I think Tarjan's off-line LCA algorithm would be best one. easy to code an fast enough always :D (maybe fastest)

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

These are by far the best tutorials I've come across:
1. Finding the lowest common ancestor in rooted trees
2. What are the specifics in implementing an O(N log N) Lowest Common Ancestor algorithm?

Both use the Binary Raising method to calculate LCA. It's the best and most intuitive approach for LCA. Most of the top programmers in my country use this.

→ Reply