Algoritmos de ÁrbolesIntermediate
Ancestro Común más Bajo (LCA)
Encuentra el nodo más profundo que es ancestro de dos nodos dados en un árbol. Operación fundamental en consultas de árboles con aplicaciones en biología computacional (evolución de especies), enrutamiento de redes y sistemas de control de versiones. Varios algoritmos ofrecen diferentes compensaciones entre tiempo y espacio.
#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
Use 'null' for empty nodes
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
500ms
SlowFast
Keyboard Shortcuts
Space Play/Pause← → StepR Reset1-4 Speed
Real-time Statistics
Algorithm Performance Metrics
Progress0%
Comparisons
0
Swaps
0
Array Accesses
0
Steps
1/ 0
Algorithm Visualization
Step 1 of 0
Initialize array to begin
Default
Comparing
Swapped
Sorted
Code Execution
Currently executing
Previously executed
Implementation