This is an old revision of the document!
# Populate Diff Tree
This algorithm is the powerhouse of project proof, and is one of the most complicated and hairy things I've ever worked on.
The purpose of this algorithm is to add information to a tree about what will change in another tree. This includes information about creation and deletion of nodes, as well as movement.
We are given two trees - an original tree and a modified tree. In the image below, the left tree is original, and the right tree is modified.
Note that both trees are linked. This means that we have decided that these two nodes are the same. The algorithm for doing this is pretty simple, but for now, you can imagine that two linked nodes are linked if they contain the same data.
(Note that I haven't drawn the links between the trees, so as to prevent clutter. Instead, nodes with the same letter are considered to be linked.)