木構造アルゴリズムIntermediate

Lowest Common Ancestor (LCA)

Finds the deepest node that is an ancestor of two given nodes in a tree. Fundamental operation in tree queries with applications in computational biology (species evolution), network routing, and version control systems. Various algorithms offer different time-space tradeoffs.

#tree#binary-tree#recursion#ancestry

Complexity Analysis

Time (Average)

O(n)

Expected case performance

Space

O(h)

Memory requirements

Time (Best)

O(n)

Best case performance

Time (Worst)

O(n)

Worst case performance

Binary Tree (level-order, comma-separated)

Use 'null' for empty nodes

Node p

Node q

Example Trees:

How it works

• Recursively traverse the tree
• Find nodes p and q in subtrees
• LCA is where both are found
• O(n) time, O(h) space
• Used in version control systems

Step: 1 / 0

Animation Speed500ms

SlowFast

Keyboard Shortcuts

Space Play/Pause← → StepR Reset1-4 Speed

Real-time Statistics

Algorithm Performance Metrics

Progress0%

Comparisons

Swaps

Array Accesses

Steps

1/ 0

Algorithm Visualization

Step 1 of 0

Initialize array to begin

Default

Comparing

Swapped

Sorted

Code Execution

Currently executing

Previously executed

Implementation

Related Algorithms

View all in 木構造アルゴリズム

Trie (Prefix Tree)

Intermediate

Tree-based data structure that stores strings efficiently by sharing common prefixes. Each path from root to leaf represents a word or key. Excels at autocomplete, spell checking, IP routing tables, and dictionary implementations with O(m) operations where m is key length.

O(m)

O(ALPHABET_SIZE × N × M)

treestring-algorithms

Start Learning

AVL Tree

Advanced

First self-balancing binary search tree invented in 1962 by Adelson-Velsky and Landis. Maintains height balance through rotations, guaranteeing O(log n) operations. Stricter balancing than red-black trees makes it ideal for lookup-heavy applications like databases and file systems.