Գտնել երկուական փնտրման ծառում տրված երկու տարրերի ամենափոքր ընդհանուր parent-ը (lowest common ancestor)։ Ալգորիթմի բարդությունը O(n):

lca

#include <iostream>
#include <queue>
#include <stdlib.h>

struct node
{
	struct node* left;
	struct node* rigth;
	struct node* parent;
	int data;
};

struct node* new_node(int d)
{
	struct node* n = (struct node*) malloc(sizeof(struct node));
	n->data = d;
	n->left = 0;
	n->rigth = 0;
	n->parent = 0;
	return n;
}

// ամենափոքր ընդհանուր անցեստորի փնտրման ալգորիթմ
struct node* lca(struct node* r, int n1, int n2)
{
	if(r == 0)
	{
		return 0;
	}
	if(r->data > n1 && r->data > n2)
	{
		return lca(r->left, n1, n2);
	}
	if(r->data < n1 && r->data < n2)
	{
		return lca(r->rigth, n1, n2);
	}
	return r;
}

int main()
{
	struct node* r = new_node(4);
	r->left = new_node(2);
	r->rigth = new_node(5);
	r->rigth->rigth = new_node(6);
	r->left->left = new_node(1);
	r->left->rigth = new_node(3);
	r->left->rigth->rigth = new_node(3.5);

	struct node* ca = lca(r, 1, 3.5);
	std::cout << "Lowest common ancestor =  " << ca->data  << std::endl;
	return 0;
}