# Revisiting the tree edit distance and its backtracing: A tutorial

arXiv: https://arxiv.org/abs/1805.06869 · HTML: https://mlsanity.com/paper/1805.06869/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 May 2018.

## Built on by (most cited first, 8 of 8)

- [Rewriting the Code: A Simple Method for Large Language Model Augmented Code Search](https://mlsanity.com/paper/2401.04514/) (2024)
- [Hierarchical Catalogue Generation for Literature Review: A Benchmark](https://mlsanity.com/paper/2304.03512/) (2023)
- [ReJump: A Tree-Jump Representation for Analyzing and Improving LLM Reasoning](https://mlsanity.com/paper/2512.00831/) (2025)
- [STED and Consistency Scoring: A Framework for Evaluating LLM Structured Output Reliability](https://mlsanity.com/paper/2512.23712/) (2025)
- [Function-to-Style Guidance of LLMs for Code Translation](https://mlsanity.com/paper/2507.11083/) (2025)
- [Hierarchical Grammar-Induced Geometry for Data-Efficient Molecular Property Prediction](https://mlsanity.com/paper/2309.01788/) (2023)
- [Information Extraction from Heterogeneous Documents without Ground Truth Labels using Synthetic Label Generation and Knowledge Distillation](https://mlsanity.com/paper/2411.14957/) (2024)
- [M3DocDep: Multi-modal, Multi-page, Multi-document Dependency Chunking with Large Vision-Language Models](https://mlsanity.com/paper/2605.18774/) (2026)

## Abstract (arXiv)

Almost 30 years ago, Zhang and Shasha (1989) published a seminal paper describing an efficient dynamic programming algorithm computing the tree edit distance, that is, the minimum number of node deletions, insertions, and replacements that are necessary to transform one tree into another. Since then, the tree edit distance has been widely applied, for example in biology and intelligent tutoring systems. However, the original paper of Zhang and Shasha can be challenging to read for newcomers and it does not describe how to efficiently infer the optimal edit script. In this contribution, we provide a comprehensive tutorial to the tree edit distance algorithm of Zhang and Shasha. We further prove metric properties of the tree edit distance, and describe efficient algorithms to infer the cheapest edit script, as well as a summary of all cheapest edit scripts between two trees.