درخت دکارتی
جستجوی کران و پایین‌ترین اجداد مشترک

درخت دکارتی می‌تواند به عنوان بخشی از داده ساختارهای کارآمد برای پرسمان‌های کمینهٔ کران و مسئله‌های جستجوی کران که در بر گیرندهٔ پرسمان‌هایی برای یافتن مقدار کمینه در یک زیر دنبالهٔ پیوسته از دنبالهٔ اصلی است، می‌باشد. در یک درخت دکارتی، این مقدار کمینه می‌تواند جد مشترک راست‌ترین و چپ‌ترین مقادیر در زیر دنبالهٔ مورد نظر باشد. به عنوان مثال، در زیردنبالهٔ (۱۵، ۲۰، ۱۰، ۱۲) در دنبالهٔ مثال زده شده در شکل (۱)، مقدار کمینه (۱۰)، پایین‌ترین جد مشترک راست‌ترین و چپ‌ترین مقادیر زیردنباله (۱۲ و ۱۵) می‌باشد. به دلیل این که پایین‌ترین جد مشترک به ازای هر پرسمان در زمان ثابتی به دست می‌آید، استفاده از داده ساختاری که حجم خطی اشغال می‌کند و در زمان خطی ساخته می‌شود، باعث می‌شود مسئلهٔ کمینه کردن کران نیز محدود به همین مرزها شود.
Bender و Farach-Colton در سال ۲۰۰۰، این رابطه بین مسئلهٔ دو داده ساختار را، با نشان دادن این که پایین‌ترین اجداد مشترک در یک درخت ورودی می‌تواند به صورت کارآمد و غیر درختی برای کمینه کردن کران حل شود، معکوس کردند. داده ساختار آن‌ها از تکنیک دور اویلری برای تبدیل درخت ورودی به یک دنباله استفاده می‌کند. پس از آن کمینهٔ کران را در دنبالهٔ به دست آمده پیدا می‌کند. دنبالهٔ حاصل از این انتقال، شکل خاصی دارد (اعداد مجاور، ارتفاع گره‌های همسایه در درخت را با اختلاف ۱± نمایش می‌دهند) که باعث برتری آن می‌شود. به منظور حل مسئلهٔ کمینه کردن برای دنباله‌هایی که این شکل خاص را ندارند، درخت دکارتی را، به منظور تبدیل مسئلهٔ کمینه کردن کران به مسئلهٔ پایین‌ترین اجداد مشترک، استفاده می‌کنند. سپس با اعمال تکنیک دور اویلری، مسئله را به مسئلهٔ کمینه کردن کران در یک دنباله که این شکل خاص را دارد، تبدیل می‌کنند.
مسئلهٔ کمینه کردن کران به این شکل می‌تواند این امکان را به ما بدهد که جستجوی کران دوبعدی را بیان کنیم. یک مجموعه از تعداد متناهی اما زیاد نقاط در صفحهٔ دکارتی می‌تواند برای شکل دادن درخت دکارتی استفاده شود. به وسیلهٔ مرتب‌سازی نقاط بر اساس مختصهٔ x آن‌ها و در نظر گرفتن مختصهٔ y آن‌ها به عنوان به عنوان ترتیب این مقادیر در دنباله، می‌توان این درخت را شکل داد. اگر S را به عنوان زیرمجموعهٔ نقاط ورودی بین چند محدودهٔ عمودی با نامعادلهٔ L ≤ x ≤ R فرض کنیم و p چپ‌ترین نقطهٔ S (نقطه‌ای که مختصهٔ x آن کمینه است) است، و q راست‌ترین نقطهٔ S (نقطه‌ای که مختصهٔ x آن بیشینه است) است، آنگاه پایین‌ترین جد مشترک p و q در درخت دکارتی پایین‌ترین نقطه در محدوده است. یک پرسمان کران سه طرفه که در آن هدف لیست کردن نقاط در یک محدودهٔ سه طرفه است که با نامعادله‌های L ≤ x ≤ R و y ≤ T مشخص می‌شود، می‌تواند با پیدا کردن پایین‌ترین نقطه (b) و مقایسهٔ مختصهٔ y آن با T، و (در صورت حضور b در محدودهٔ مورد نظر) ادامه دادن این روش بین b و p، و بین b و q، به صورت بازگشتی، پیدا شود. در این روش پس از این که راست‌ترین و چپ‌ترین نقاط بازه مشخص شدند، تمام نقاط بین این سه محدوده را می‌توان در زمان ثابت به ازای هر نقطه، لیست کرد.
در ساختمان به این شکل برای پایین‌ترین اجداد مشترک در یک درخت دکارتی، این امکان را ایجاد می‌کند که داده ساختاری با اشغال حجم خطی بسازیم که به ما اجازهٔ پرسش ذر مورد فاصلهٔ بین هر جفت از نقاط در فضای فرامتریک را در زمان ثابت به ازای هر پرسمان، می‌دهد. فاصلهٔ بین دو نقطه در فضای فرامتریک، وزن مسیر مینیماکس در درخت فراگیر کمینه در فضای متریک است. از یک درخت فراگیر کمینه می‌توان یک درخت دکارتی ساخت که ریشهٔ آن نمایانگر سنگین‌ترین لبهٔ درخت فراگیر کمینه می‌باشد. با تقسیم درخت فراگیر کمینه به دو زیردرخت، می‌توان به صورت بازگشتی درخت دکارتی را به وسیلهٔ بچه‌های ریشهٔ ذکر شده ساخت. برگ‌های درخت دکارتی، بیان‌گر نقاط فضای متریک هستند. همچنین پایین‌ترین جد مشترک دو برگ، سنگین‌ترین لبه بین آن دو نقطه در درخت فراگیر کمینه است که وزن آن با فاصلهٔ بین دو نقطه برابر است. درخت دکارتی زمانی می‌تواند در زمان خطی ساخته شود که درخت فراگیر کمینه را بیابیم و وزن لبه‌های آن را مرتب کنیم.