/* Tree-ში ყველაზე პატარა საერთო წინაპარი O(1) მეხსიერებით აღწერა მოცემულია ბინარული ხე (ძებნის გარეშე): struct Node { Node* parent; Node* left; Node* right; } საჭიროა დაწეროთ ფუნქცია, რომელიც ორი მონაცემი კვანძისთვის დააბრუნებს მათ ყველაზე პატარა (მახლო) საერთო წინაპარს: Node* Lca (Node* a, Node* b); */

ორი წერტილის უახლოესი საერთო წინაპრის (LCA) მოძიება ბინარულ ხეზე, სადაც არსებობს მშობელთა პინჩერები და დამატებითი მეხსიერება არ არის, შესაძლებელია შემდეგი მიდგომით:

1. გამოითვალეთ თითოეული ორი წერტილის სიღრმე.
2. ამ სიღრმის უფრო ღრმა წერტილი აიწიეთ მშობელთა ჯაჭვით, სანამ სიღრმეები არ თანხვედრიან.
3. შემდეგ, ერთდროულად ასწიეთ ორივე წერტილის მშობელთა ჯაჭვით, სანამ არ შეხვდებიან — ეს იქნება LCA.

მაგალითი Go-ში:

type Node struct {
    parent *Node
    left   *Node
    right  *Node
}

func depth(n *Node) int {
    d := 0
    for n != nil {
        n = n.parent
        d++
    }
    return d
}

func Lca(a, b *Node) *Node {
    da := depth(a)
    db := depth(b)

    // აიწიეთ უფრო ღრმა წერტილი
    for da > db {
        a = a.parent
        da--
    }
    for db > da {
        b = b.parent
        db--
    }

    // ერთდროულად ასწიეთ, სანამ არ შეხვდებით საერთო წინაპარს
    for a != b {
        a = a.parent
        b = b.parent
    }
    return a
}

ეს ალგორითმი იყენებს მხოლოდ პინჩერებს და კონსტანტურ მეხსიერებას, მუშაობს დროით O(h), სადაც h ხის სიმაღლეა.